Sort.md

Sort | 정렬

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

• 각 정렬 알고리즘의 시간복잡도를 비교하는데, 시간복잡도에 대해 학습이 필요하신 분은 여기를 참고하세요

Sort 종류

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 병합 정렬(Merge Sort)
• 계수 정렬(Counting Sort)

• Time Sort

Bubble Sort | 버블 정렬

시간복잡도 : O(N²)

• 배열의 처음부터 끝까지 두 수(a, b)를 선택한 뒤 정렬되어 있지 않으면 두 수의 위치를 변경한다.
• 구현 코드 보러 가기

Selection Sort | 선택 정렬

시간복잡도 : O(N²)

• N + (N-1) + (N-2) + ... + 1 = N*(N-1)/2 (등차수열의 합 공식) 이므로 O(N²)
• 정렬되지 않은 데이터 중 가장 작은(큰) 수를 정렬된 수들 가장 뒤에 붙여가며 정렬한다.
• 구현 코드 보러 가기

Insertion Sort | 삽입 정렬

시간복잡도 : O(N²), Ω(N)

• 맨 처음 데이터와 정렬할 차례가 된 수의 앞은 항상 정렬되어 있다고 가정하고 시작한다.
• 데이터를 순서대로 방문하며 앞의 수가 본인보다 작을 때까지 앞 숫자와 순서를 바꾼다.
• 구현 코드 보러 가기

Quick Sort | 퀵 정렬

시간복잡도 : O(N²), Ω(NlogN)

• 가장 많이 사용되는 정렬 알고리즘. 프로그래밍 언어 정렬 라이브러리의 근간이기도 하다.
• 최악의 시간복잡도 O(N²)는 내림차순이나 올림차순으로 이미 정렬이 되어 있는 경우 발생
• 피벗 수를 하나 특정하여 정렬되지 않은 수들 중 피벗보다 작은 숫자를 왼쪽에서 부터 찾고 피벗보다 큰 수를 오른쪽에서 부터 찾는다.
• 구현 코드 보러 가기

Merge Sort | 병합 정렬

시간복잡도 : O(NlogN), Ω(NlogN)

Counting Sort | 계수 정렬

데이터의 최대값이 K일 때
시간복잡도 : O(N + K)
공간복잡도 : O(N + K)

• 다른 정렬 알고리즘들고 다르게 데이터끼리 비교 연산을 하지 않는다.
• 모든 데이터가 정수값을 가지면서 최소값과 최대값의 차이가 크지 않을 때 효율적이다.
• 최소값부터 최대값의 차이만큼의 리스트(또는 배열)를 0으로 초기화한다.
• 모든 데이터르 방문하며 해당 하는 인덱스 배열에 삽입한다.
• 이후 리스트의 값이 0이 아닌 인덱스 번호를 해당 값만큼 반복하여 출력한다.

Time Sort

시간복잡도 : O(NlogN), Ω(N) Python의 'sort', 'sorted' 함수의 정렬 알고리즘이다.

출처 시간복잡도 표 : https://velog.io/@jaeyunn_15
버블 정렬 : https://medium.datadriveninvestor.com/bubble-sort-in-javascript-298375020b29
선택 정렬 : https://burning-camp.tistory.com/89
삽입 정렬 : https://thinkdiff.net/insertion-sort-swift-db14b9a79016
퀵 정렬 : https://velog.io/@yun8565
합병 정렬 : https://velog.io/@yun8565
계수 정렬 : https://herong.tistory.com/entry/계수정렬Counting-Sort