Sorting (Bubble, Selection, Insertion Sort)

대부분 정렬의 시간복잡도는 O(n·logn)와 O(n²) 사이임

특별한 경우 O(n)까지 가능

Internal sorting - main memory 에서 일어나는 정렬

External sorting - secondary storage(하드디스크) 에서 일어나는 정렬

Bubble Sort

이웃되는 값끼리 비교하여 자리를 변경해나가는 방식

기본적으로 O(n²). 이미 정렬이 되어 있을 경우는 O(n)

예시

예시2

Selection Sort

array에서 가장 큰 수를 찾은 다음, 찾은 수를 어레이의 맨 끝인 n자리에 놓는다.

다음 큰수를 찾은 다음, 어레이의 n-1자리에 넣는다. 이때 찾은 수와 해당 자리에 있는 수의 자리를 바꾼다.

O(n²)의 performance가 나옴

• bubble sort와 똑같이 O(n²)이지만 bubble sort에 비해 값의 교환 수가 적음

이미 정렬이 되어 있어도 O(n²)임

예시

예시2

Insertion Sort

새로운 키를 넣을 때, 정렬을 하고 있는 어레이에서 자신이 어디에 들어가야 할지 결정한 다음 맞는 자리에 넣는다.

performance: O(n²) 이미 모든 키가 정렬되어 있으면 O(n)

짧은 list에서 단순하고 좋음.
이미 부분적으로 정렬이 되어 있는 경우에 좋다

예시

예시2

Selection Sort vs Insertion Sort

Selection Sort는 정렬되어있지 않은 수를 전부 확인 해 가장 큰 수를 찾아야 함

• 정렬이 전부 되어 있어도 모든 수를 비교

Insertion Sort는 정확한 위치에 들어가는 것을 결정하기 위해 정렬 중인 어레이를 확인 해야 함

• 필요한 값만 읽고 정렬된 리스트에서 비교

n개의 element가 있다고 가정할 때, Selection은 n번만 쓰면 됨. 뒤에서부터 쓰기 때문에 어레이의 key들이 이동할 필요가 없지만, Insertion은 key들이 전부 이동할 수도 있기 때문에 write가 더 많이 일어남

• 예를 들어, 2 3 4 5 1 의 값을 Insertion Sort로 정렬한다고 하면, 마지막 1을 정렬하기 위해 2 3 4 5 의 값이 한 칸씩 이동해야함

만약 write비용이 비쌀 경우 (예를 들어, flash memory) Insertion Sort보단 Selection Sort이 더 좋음

요약

• bubble, selection, insertion sort의 시간복잡도 worst case는 O(n²)
• 만약 전부 정렬된 리스트를 비교한다면 bubble, insertion sort는 O(n)이지만 selection은 여전히 O(n²)