[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 06 정렬 - 기준에 따라 데이터를 정렬

기준에 따라 데이터를 정렬

 

1 _ 정렬 알고리즘 개요

1. 정렬(Sorting)
   • 데이터를 특정한 기준에 따라서 순서대로 나열
   • 이진 탐색의 전처리 과정

 

---

 

2 _ 선택 정렬

1. 선택 정렬
   • 데이터가 무작위로 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다.
   • 그 다음 작은 데이터를 선택해 두번 때 데이터와 바꾼다.
   • 위 과정을 반복한다.
2. 선택 정렬 그림 설명

 

3. 선택 정렬 소스 코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i

    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min-index = j

    array[i], array[min_index] = array[min_index], array[i]

print(array)

 

4. 선택 정렬 시간 복잡도

• O(N^2)

 

---

 

3 _ 삽입 정렬

1. 삽입 정렬
   • 데이터를 하나하나 확인한 후, 각 데이터를 적절한 위치에 삽입한다.
2. 삽입 정렬 그림 설명

 

3. 삽입 정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in rnage(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break


print(array)

 

4. 삽입 정렬 시간 복잡도

• O(N^2)

 

---

 

4 _ 퀵정렬

1. 퀵 정렬
   • 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
2. 퀵 정렬 그림 설명

• 초기 데이터

• 1 파트

• 2 파트

• 3 파트

 

3. 퀵 정렬 소스코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right:

        while left <= end and array[left] <= array[pivot]:
            left += 1

        while right > start and array[right] >= array[pivot]:
            right -= 1

        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]


       quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)


quick_sort(array, 0, len(array)-1)
print(array)

 

4. 퀵 정렬 시간 복잡도

• O(NlogN)

 

---

 

5 _ 계수 정렬

1. 계수 정렬
   • 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
   • 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보는 담는다.
2. 계수 정렬 그림 설명

 

출력 결과

 

 

3. 계수 정렬 소스코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array) + 1)
    count[array[i]] += 1


for i in range(len(count)):
    for j in range(count[i]):
        print(i, end = ' ')

 

4. 계수 정렬 시간 복잡도

• O(N+K)

 

---

 

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬