1. 선택 정렬.



제일 작은 값을 '선택'하여 맨 앞 위치(정렬이 안된 위치)와 바꿈


출처 : http://terms.naver.com/entry.nhn?docId=2270435&cid=51173&categoryId=51173




2. 버블 정렬




맨 앞(정렬이 안된 위치)부터 맨 뒤까지 이어진 두 값을 비교하여 정렬되도록 스위치함

'거품이 상승하는 것처럼' 값을 바꿔감


출처 : http://terms.naver.com/entry.nhn?docId=2270437&cid=51173&categoryId=51173



3. 삽입 정렬



두번 째 값부터 정렬함

값을 선택하여 현재 위치에서 '바로 앞의 값과 비교'

자신보다 작거나 같은 값을 만날 때까지 값을 바꿔감


출처 : http://terms.naver.com/entry.nhn?docId=2270436&cid=51173&categoryId=51173




4. 합병 정렬 (=병합 정렬)


주어진 배열을 두 집단으로 나누어 순서를 매기는 방식

모든 원소를 나누고 두 개씩 짝지어서 대소 비교 후 정렬함

결과로 나온 정렬된 두 원소를 같는 집단들을 두 개씩 짝짓고 또 정렬

이 과정을 반복


장점 : 구현이 쉽고 앞서 소개한 알고리즘들 보다 월등히 빠름 (= 가성비 굳) (시간복잡도 = O(n logn))


반드시 외워서 언제든 구현할 줄 알아야한다고 생각함.




5. 퀵 정렬


정렬 순서가 합병 정렬과 반대임

주어진 배열에서 맨 앞 원소를 '기준 키'로 정한다.

기준 키를 제외한 나머지 값에 대해 정렬이 이루어지는데, 맨 앞에서부터 값을 선택하는 인덱스 a와 맨 뒤에서부터 값을 선택하는 인덱스 b를 정의한다.

인덱스 a는 기준 키보다 작은 값을 발견하면 다음으로 넘어가고,

인덱스 b는 반대로 기준 키보다 큰 값을 발견하면 다음으로 넘어간다.

인덱스 a가 가리키는 값(기준 키 보다 큰 값)과 인덱스 b가 가리키는 값(기준 키 보다 작은 값)을 스위칭한다.

이러다가 두 인덱스가 교차하게 되면 더이상 스위칭하지 않고 인덱스 b가 가리키는 값(기준 키 보다 작은 값)을 기준 키와 스위칭한다.


이 과정을 거치면 기준 키로 선택되었던 값을 기준으로 왼쪽과 오른쪽이 작은쪽, 큰쪽으로 나뉘게 된다.

이 때 기준 키를 제외한 왼쪽 부분과 오른 쪽 부분에 대해 위 과정을 반복한다.

최종적으로 각 원소 단위로 나뉘게 되면 정렬이 완료된다.


상당히 복잡하지만 최적의 속도는 합병 정렬과 같다. (O(n logn))

하지만 아이러니하게도 이미 정렬된 배열이 주어졌을 때 제일 오래걸린다. (O(n^2))

[합병 정렬은 언제나 O(n logn)임]


C++같은 경우 퀵 소트 라이브러리를 지원해 주기 때문에 꽤 잘쓰이는 것 같다. (잘 모름)



+ Recent posts