[python]정렬 알고리즘

💢 정렬 알고리즘

💢선택정렬

리스트가 아래와 같이 있을때 선택정렬을 적용 시켜보자

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

• [✅step0]: 처리되지 않은 데이터중 가장 자근 '0'을 선택해 가장 앞의'7'과 바꿔준다.
  [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
• [✅step1]: 처리되지 않은 데이터 중 가장 작은 '1'을 선택해 가장 앞의 '5'와 바꿔준다.
  [0, 1, 9, 7, 3, 1, 5, 2, 4, 8]
• [✅stpe2]: 처리되지 않은 데이터 중 가장 작은'3'을 선택해 가장앞의'7'과 바꿔준다.
  [0, 1, 2, 7, 3, 1, 5, 9, 4, 8]

위와 같은 작업을 반복하다 보면 아래와 같은 형식으로 나타내어 진다.

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

위와 같은 처리를 아래와 같은 코드로 구현해보자

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

for i in range(len(array)): #array의 인덱스를 i로 뽑아온다
    min_index = i    최소값을 의미하는 변수에 인덱스르 넣어준다.
    for j in range(i+1, len(array)): #비교하려고 하는 인덱스에 +1를 해주어 그 다음숫자부터 끝까지 비교할 수 있도록 구현

        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)    

💢삽입정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택정렬에 비해 구현 난이도가 높지만, 속도가 더 빠름

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

• [✅step 0]: 첫번째 데이터 '7'은 정렬이 되어있다고 가정하고 두번째 수인 '5'가 어떤 위치로 들어갈지를 판단. '7'의 왼쪽으로 들어가거나 오른족으로 들어가거나 두 경우만 존재

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

• [✅step 1]: '9'가 어디로 들어갈지 판단
  (그대로 있음)

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

• [✅step 2]: 이어서 0도 값을 찾아 들어간다.

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

• [✅step3]: '3'도 자기 위치를 찾아간다.

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

위와같은 작업을 반복하다보면 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]로 나열된 리스트를 뽑아낼 수 있다.

그러면 이제 코드로 어떤식으로 구현할 수 있는지 확인해보자

코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
    for j in range(i, 0, -1): #왼쪽으로 이동하며 값을 비교
        if array[j-1] > array[j]: #왼쪽에 수가 더 클 경우
            array[j-1], array[j] = array[j], array[j-1] # 위치를 바꿔줌
        else:
            break
print(array)

💢 퀵 정렬

• 기준 데이터를 서렂아혹 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준으 데이터(Pivot)로 설정

어떤식으로 진행되는지 리스트로 나타내보자!

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

• [✅step 0]: 첫번째 숫자인 5를 피벗으로 설정하고 왼쪽에서부터는 큰숫자를, 오른쪽부터는 '5'보다 작은 숫자를 찾아나간다.
  '5'보다 큰숫자: 7
  '5'보다 작은숫자: 4
  저 위에 두개의 자리를 바꿔준다

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

• [✅step 1]:
  '5'보다 큰 숫자: 9
  '5'보다 작은숫자: 2
  두 개의 위치를 바꿔준다

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

• [✅step 2]:

'5'보다 큰 숫자: 6
'5'보다 작은 숫자: 1
※ 이 경우 왼쪽으로 부터 찾을때, 오른쪽으로 부터 찾을때 크로스 된 것을 알 수 있다. 이럴 경우 작은값('1')과 피벗('5')의
위치를 바꿔준다. 그렇지 않을 경우 작은값('1')과 큰값('6')의 위치를 바꿔준다.

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

이렇게 되면 첫 피버값을 기준으로 왼쪽은 피벗보다 작은 수, 오른쪽은 피벗보다 큰 숫자로 정렬이 되는 것을 알 수 있다. 이러한 작업을 분할(Divide)이라고 한다.

왼쪽에 있는 데이터, 오른쪽에 있는데이터들을 각각의 배열로 판단을해 각각 큌 정렬을 수행해준다.
[1, 4, 2, 0, 3] [6, 9, 7, 8]
이렇게 나누어 주고 1을, 6을 피벗으로 설정해 각자 재귀적으로 진행해준다.

위에 모든 과정들을 코드로 나타내보자

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

def quick_sort(array, start, end):
    if start >= end: #원소가 1개인 경우 종료
        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)

Comprehnesion문법을 이용하면 훨씬 더 효율적으로 코드를 작성할 수 도 있다.

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

def quick_sort(array):

    if len(array) <= 1:
        return array
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [ y for y in tail if y> pivot]
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

훨씬 더 보기도 편하고 이해도 편한 형태인거 같다. 왼쪽리스트 피벗보다 작은수들을, 오른족 리스트에 피벗보다 큰수들을 담아 중간에 피벗을 삽입해 리턴시주면 된다.

💢계수 정렬

• [✅step 0]: 가장 작은 데이터로부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트 생성
• 정렬할 데이터: 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

인덱스	0	1	2	3	4	5	6	7	8	9
계수	0	0	0	0	0	0	0	0	0	0

앞에서 부터 수를 처리할때 그 숫자의 인덱스 값을 찾아가 count에 1을 누적시켜주면 0 부터 9까지 각각 몇개의 수가 있는지를 뽑을 수 있다.

인덱스	0	1	2	3	4	5	6	7	8	9
계수	2	2	2	1	1	2	1	1	1	2

코드

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

count = [0] * len(array)
for i in range(len(array)): #각 데이터에 해당하는 인덱스의 값 증가
    count[array[i]] += 1

for i in range(len(array)):
    for j in range(count[i]): #count된만큼 반복해서 출력
        print(i,end = " ")

print(count)
>>>0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

참고자료: https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4