기본 정렬 (sort) 알고리즘

 

인터뷰 단골 주제인 기본정렬 알고리즘을 정리해보자. 

단순이 이렇게 풀면 된다, 에서 더 나아가서 어떤 해결방법이 다른 해결방법에 비해 가지는 장점과 단점을 함께 비교해보면 좋다. 

 

 정렬 알고리즘에는 크게 내부 정렬 방식 과 외부정렬 방식으로 나눠진다. 

 

 - 내부 정렬 방식은 외부 보조 기억 공간을 활용하지 않는 것으로,

Selection, Bubble, Quick, Insertion Sort 가 있다. 

 

 - 외부 정렬방식은 대용량 자료 처리에 적합하고, 병합방식이 쓰인다. 

 

 

---

 

가장 흔히 쓰이고 빠른 알고리즘

Quick Sort가 평균적으로 가장 좋은 성능을 낸다. 

이미 정렬되어 있을 경우에는 Insertion Sort가 제일 빠르다. (바로 앞자리 한번만 비교하면 되기 때문)

 

시간 복잡도 

O(n**2) : Bubble Sort, Selection Sort, Insertion Sort, Shell Sort, Quick Sort

O(n log n) : Heap Sort, Merge Sort

O(kn) : Radix Sort

 

 

 

 

---

 

Bubble Sort

버블 소트는 인접한 두개의 원소를 비교해서, 더 큰 값을 뒤로 보낸다. (이는 오름차순인지/ 내림차순인지에 따라 달라진다.)

 

python 으로 백준 2750 번을 Bubble Sort를 사용해서 풀어보았다. 

 

from sys import stdin

# n = int(input())
# arr = input()
# l = list(map(int,arr.split(' ')))


n = int(input())
arr = [int(input()) for i in range(n)]

# Bubble Sort

for i in range(len(arr)):
    for j in range(0, len(arr)-i-1, 1):  # Push the biggest number to the end
        if arr[j] > arr[j+1]:
            k = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = k  # Swap two numbers

for i in range(len(arr)):
    print(arr[i])

 

다음장부터는 Quick Sort와 Merge Sort를 추가하려고 한다.