[sort 시리즈 intro][ 작성중 ] sorting algorithm (with. python3)

31 Oct 2018

Reading time ~2 minutes

이 컨텐츠는 시리즈물입니다.

[sort 시리즈 intro]
- sorting algorithm (with. python3)
  - https://joosjuliet.github.io/sort/
[sort 시리즈]
- [sort 시리즈 1탄] [merge sort] sort algorithm with python3
  - https://joosjuliet.github.io/merge_sort/
- [sort 시리즈 2탄] 삽입정렬(insertion sort) with python3
  - https://joosjuliet.github.io/insertion_sort/
[sort 시리즈 번외편]
- [python] python의 기본 sort tim_sort란!
  - https://joosjuliet.github.io/tim_sort/

알고리즘을 시각화 해서 보여주는 tool

https://visualgo.net/en/sorting

정렬 알고리즘 종류와 특징

구현은 쉽지만 실행시간이 긴 것 : 1. Selection Sort, 2. Bubble Sort 구현은 어렵지만 실행시간이 짧은 것 : 3. Merge Sort, 4. Quick Sort, 5. Time Sort

Stable Sort란?

정렬 후 기존의 순서가 유지되는 정렬을 Stable Sort라고 한다.

머지정렬, 버블 정렬, 삽입 정렬은 Stable하다.
- 정렬 전
- 정렬 후(이 때 초기에 2(1)과 2(2)의 순서는 유지되는 것을 알 수 있다.)

Unstable Sort란?

정렬 후 기존의 순서가 유지되지 않는 정렬은 Unstable Sort라고 한다.

퀵정렬, 힙정렬, 선택정렬

Selection Sort

평균 및 최악 실행 시간: O(N^2) 메모리: O(1)

탐색을 하면서 찾은 작은 원소를 배열 맨 앞으로 보내는 것이다. 계속 차례대로 다음 작은 애를 찾아서 앞으로 보낸다.

Bubble Sort

평균 및 최악 실행 시간: O(N^2) 메모리: O(1)

버블 정렬은 배열의 첫 원소부터 순차적으로 진행하며, 현재 원소가 그 다음 원소의 값보다 크면 두 원소를 바꾸는 작업을 반복하나. 이런식으로 배열을 계속 살펴보면서 완전히 정렬된 상태가 될 때까지 반복한다.

n은 a의 길이

for i in range(1, n):
    for j in range(i, n-1):
        if a[j] > a[i]:
            a[i], a[j] = a[j], a[i]

Merge Sort

평균 및 최악 실행 시간: O(NlogN) 메모리: O(N)

merge_sort

합병 정렬의 단계

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열들을 정렬한다.(일명 서열정리) 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정복을 통해 생긴 만들어진 코드블럭들을 합치는 행동을 한다.

1) 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다. 2) 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다. 3) 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다. 4) 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

결국, 정렬된 부분 배열들을 하나의 배열에 합병한다.

Quick Sort

평균 및 최악 실행 시간: O(NlogN)

재귀를 이용한 분할정복 알고리즘 특정 pivot이라는 기준을 새워, pivot 기준 작으면 왼쪽 크면 오른쪽 퀵 소트의 최악의 경우는 O(N^2)

피봇 정하고
기준 작으면 왼, 크면 오
정렬 될때까지 왼,오 나누어 분할

Tim Sort

O(NlogN)

python에서 쓰는 sort는 time sort이다. quick sort를 안쓰는 이유는 정렬 됬을 시 time complexity가 높을 가능성 때문이다. 그래서 big O의 성능이 평균적으로 좋은 O(NlogN)을 사용한다. (작성중)https://joosjuliet.github.io/tim_sort/ 작성중이지만 일단 따로 포스팅을 해놨다

참고자료

http://vcdstr.knou.ac.kr/vcdstr/vcd/e_s/Y/234525/M3452512104004/sum01.htm

[Merge Sort 사진자료, 내용 ]출처 및 참고자료 https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
stable sort내용
https://goodgid.github.io/Stable-Sort/#:~:text=%EC%A0%95%EB%A0%AC%20%ED%9B%84%20%EA%B8%B0%EC%A1%B4%EC%9D%98%20%EC%88%9C%EC%84%9C,%EC%9D%84%20Stable%20Sort%EB%9D%BC%EA%B3%A0%20%ED%95%9C%EB%8B%A4.

computer_science