[내일배움캠프 Day29] 정렬

https://www.youtube.com/playlist?list=PLDV-cCQnUlIZXLSUeF2Fav3_7X7ku-F63

코딩테스트 Sorting

 

코드없는 프로그래밍 유튜브와 뇌를 자극하는 알고리즘 책을 보면서 정렬 알고리즘에 대해 공부했습니다. 정렬 내용이 많아 O(n^2) 를 가지는 버블, 삽입, 선택 정렬만 정리해보겠습니다.

 

Bubble Sort (버블 정렬)

데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행합니다. 

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

버블 정렬은 데이터 집합을 한번 순회할 때마다 정렬해야 하는 데이터 집합의 범위가 하나씩 줄어들므로, 버블 정렬의 비교 횟수 = (n-1)+(n-2)+(n-3)+...+3+2+1 = n(n-1)/2 이므로 $O(n^2)$  입니다. 그리고 Stable Sort 입니다.

 

Insertion Sort (삽입 정렬)

삽입 정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘입니다.

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html

삽입 정렬은 비교 횟수가 버블 정렬하고 똑같지만 데이터 집합이 정렬되어 있는 경우에는 한번도 비교를 거치지 않습니다. 데이터가 정렬되어 있는 최선의 경우와 역으로 정렬되어 있는 최악의 경우에 삽입 정렬이 수행하는 비교 횟수의 평균을 낸다면 ( n(n-1)/2 + (n-1) ) / 2 = n^2+n-2 / 2 회 정도가 됩니다. 이는 버블 정렬과 삽입 정렬의 성능이 똑같아 보이지만, 평균적으로는 삽입 정렬이 더 나은 성능을 보인다는 뜻으로 비교적 크기가 작은 데이터 집합을 정렬하는 루틴을 작성할 때는 삽입 정렬을 사용할 것을 권합니다. 또한 Stable Sort 입니다.

 

Selection Sort (선택 정렬)

선택 정렬은 전체 배열에서 최솟값을 찾아 맨 앞부터 순서대로 채워나가는 정렬 방식입니다.

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

선택 정렬도 버블 정렬과 마찬가지로 (n-1)+(n-2)+(n-3)+...+3+2+1 = n(n-1)/2 이므로 $O(n^2)$  입니다. 동일한 값의 상대적 위치가 바뀔 수 있는 Unstable Sort 입니다.

 

 

출처 : 코드없는 프로그래밍 유튜브, 뇌를 자극하는 알고리즘 책, https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html