본문 바로가기

Algorithm/Sorting algorithm

 (3)
퀵 정렬 (Quick Sort) 퀵 정렬은 분할 정복 알고리즘의 하나이다. 평균적으로 다른 정렬에 수행 속도가 빠른편이다. 분할정복 알고리즘은 문제를 2개로 분리하고 각각 해결한 후 그 해결 결과값을 모아서 원래의 문제를 해결하는 방식이다. 퀵 정렬의 과정은 다음과 같다. 리스트에서 임의의 원소를 고른다. 이 원소를 pivot이라 칭한다. pivot을 기준으로 좌측은 pivot보다 작은 수, 우측은 pivot 보다 큰 수가 오도록 서로 교환한다. 분할된 두 개의 리스트에 대해 재귀적으로 반복한다. '5,2,4,6,7,1,3' 를 퀵정렬 했을때 가장 좌측 5를 pivot으로 설정하고, 2을 left, 3을 right로 설정 left는 => 방향으로 이동하며 pivot보다 큰값 찾기, right는
선택정렬 (Selection sort) 선택정렬 (Selection sort)은 데이터 전체에서 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하는 방식으로 정렬한다. 버블정렬은 인덱스를 이동하면서 교환이 필요하면 즉시 교환했다. 하지만 선택정렬은 두항을 비교하고 작은 값이 저장된 요소값이 아닌 그 배열의 인덱스를 따로 저장한다. 그리고 단계가 끝마칠때 단 한번만 교환한다. 5,1,3,4,2 선택정렬 (오름차순)으로 정렬하기! 1단계 5 [0] 1 [1] 3 [2] 4 [3] 2 [4] 선택된 항 = 0번째 인덱스 (현재 기준점 [0] ) 0번째 1번째항 비교, 값은 그대로 두고 기준점만 변경 현재 기준점이 ( [1] )로 변경됨 이후 기준점 [1] 을 기준으로 나머지 2,3,4번째 항을 비교함 이후 마지막으로 최초 기준인덱스였던 0번째 인..
버블 정렬 (Bubble Sort) 버블 정렬(Bubble Sort)은 서로 연접한 두 항으 계속해 비교하는 방식이다. n번째 항이 있다고 가정할때 0번째 항과 1번째 항 비교, 1번 항 2번 항 비교, 2번 항 3번 항 비교해서 마지막 두항 n-1번 항 n 번항을 비교후 마지막 항의 정보가 결정된다. 오름차순으로 정렬할 경우 가장 큰값을 먼저 결정하는 특징이 있다. `3, 4 ,1 ,5 ,2` 를 버블정렬 해보겠다. 1단계 0번항 1번항 비교 (유지) 3 4 1 5 2 1번항과 2번항 비교 (교환) 3 1 4 5 2 2번항과 3번항 비교(유지) 3 1 4 5 2 3번항과 4번항 비교(교환) 3 1 4 2 5 1단계 완료 2단계 다시 0번항 1번항 비교 (교환) 3 1 4 2 5 1번항과 2번항 비교 (유지) 1 3 4 2 5 2번항과 3..

티스토리툴바