기본 정렬 중에 네 번째는 quick sort 입니다.




quick sort 의 핵심 개념은 pivot 입니다.


리스트의 element 중에서 아무 element 나 뽑았을 때 그 값은 정렬 했을 때 가장자리 보다는 중간정도 위치에 들어갈 확률이 더 높습니다.


그 수를 중심으로 양쪽으로 나누어서 정렬하는 것이 quick sort인데 여기서 랜덤으로 뽑은 수를 pivot으로 사용합니다. 


(여기서는 구현의 편의를 위해서 가장 마지막 element 를 pivot으로 사용했고, 그렇기 때문에 정렬되어 있는 경우는 시간 복잡도가 n**2 이 될 수 있습니다.)



리스트의 길이가 1이 될 때 까지 pivot을 기준으로 양쪽으로 나누고 O(log n), pivot이 자리를 잡는데 O(n)의 시간이 필요합니다.


리스트를 나눠가면서 정렬을 하기 때문에 평균 시간복잡도가 O(nlogn) 이 됩니다.



시간복잡도: O(nlogn)  최악의 경우 O(n^2)(정렬되어 있는 경우)


공간복잡도: O(1) 


을 필요로 합니다.



또, 구현하는데 recursive 재귀 개념이 들어가 있어서 인터뷰에서도 자주 출제되는 알고리즘이기 때문에 


에디터 환경 뿐만아니라 구글 닥스나 손으로 코딩을 작성해보시는 것 을 추천드립니다.



코드는 다음과 같습니다.





혹시, 잘못된 부분이 있으면 언제든지 댓글 남겨주세요!


감사합니다.


  1. 일산헤이터 2017.11.28 08:26 신고

    요즘 게시글이 뜸하십니다.

세 번째는 merge sort 입니다.



merge sort 의 핵심 개념은 divide and merge 입니다.


리스트의 길이가 1이 될 때 까지 반으로 나누고 O(log n), 리스트를 합치면서 정렬을 하는 알고리즘입니다.



시간복잡도: O(nlogn)


공간복잡도: O(n) 


을 필요로 합니다.



또, 구현하는데 recursive 재귀 개념이 들어가 있어서 인터뷰에서도 자주 출제되는 알고리즘입니다.



코드는 다음과 같습니다.





이상입니다.



 

두 번째는 선택 정렬(selection sort) 입니다.





선택 정렬은 가장 작은 수를 선택해서 순서대로 배치하는 방법의 알고리즘입니다.



즉, n개의 element를 갖는 리스트에서 n개를 순회하면 가장 작은수를 찾을 수 있는데 이 수를 맨 왼쪽에 두고, 다음은 n-1개의 엘리먼트에서 가장 작은수를 찾아서 첫 번째 찾았던 가장 작은 수 의 오른쪽에 두면 됩니다.


이렇게 연산 횟수는 n+ (n-1) + ... + 1 = n(n+1)/2 되므로 시간복잡도는 O(n^2) 이 됩니다.


시간 복잡도는 버블 정렬과 같고, 공간복잡도는 최소값을 저장할 공간이 필요하므로 O(1)이 필요합니다.



시간복잡도 : O(n**2)


공간복잡도: O(1)



파이썬으로 선택 정렬을 구현하고 테스트 한 코드를 공유 하도록 하겠습니다.


테스트하는 습관은 항상 가지시면 나중에 큰 도움이 될거라고 생각합니다.








혹시, 잘못된 부분이 있으면 언제든지 댓글로 가르쳐주시면 감사하겠습니다.


감사합니다 !






오늘부터 기본 리스트의 정렬 알고리즘들에 대하여 정리해보도록 하겠습니다.


Python 을 이용하여 구현 하도록 하겠습니다.



가장 먼저, 버블 정렬 입니다.



버블 정렬은 


시간 복잡도 O(N^2)


공간 복잡도 O(1)


으로 성능이 떨어지는 알고리즘입니다. 옆 인덱스의 수들과 비교해서 버블 정렬 이라고 합니다.



N - 1 번 첫 인덱스 부터 끝에서 두 번째 인덱스의 수까지 옆에 인덱스의 값과 비교하면서 정렬해 나가면됩니다.


코드입니다.




감사합니다.








+ Recent posts