[파이썬 기초] 알고리즘 - 정렬

🔍  정렬 알고리즘

- 파이썬에는 내장 정렬 메소드 sort 가 있지만, 코딩을 하다보면 내장 메소드로만은 해결 불가능한 경우가 있다.

- 정렬 알고리즘은 시간 복잡도에 따라 성능을 좌우되며 성능이 좋을수록 구현 방법이 어려워진다.

 

1) O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)

• 버블 정렬(Bubble Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort)

2) O(n log n)의 시간 복잡도

• 병합 정렬(Merge Sort)
• 퀵 정렬(Quick Sort)

---

 

🗝 버블 정렬(Bubble Sort)

- 처음부터 끝까지 인접하는 인덱스의 값을 순차저그로 비교하면서, 큰 숫자를 가장 끝으로 옮김.

- 거품 정렬은 안정 정렬이며, 개인적으로 구현 방법이 가장 단순하다.

버블 정렬 과정

무작위로 가져오기

array = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트 생성

def bubble_sort(array):
    length = len(array) -1   #4
    for i in range(length): # 리스트의 크기(0-3)만큼 반복
        for j in range(length - i): # 각 회전당 정렬이 끝나지 않은 친구들을 위해 반복(4-1)
            if array[j] > array[j + 1]: # 현재 인덱스의 값이 다음 인덱스의 값보다 크면 실행
                array[j], array[j + 1] = array[j + 1], array[j] # swap해서 위치 바꾸기
        인쇄(배열)

print( "앞: " , 배열)
버블 정렬(배열)
print( "뒤:" , 배열)

[정렬] 키순대로 배열

---

 

🗝 삽입 정렬(Insertion Sort)

- 정렬되어 있는 자료배열과 비교하여 정렬 위치를 찾음. 구현이 간단.

- 삽입 정렬은 안정 정렬이며, 값의 양이 길어질수록 효율이 떨어짐.

삽입정렬 과정

import random

array = random.sample(range(1, 10), 5)
def insertion_sort(array): #arr = [5,10,2,1,0]

	n = len(array)    
	for i1 in range(1, len(array)): 
		i2 = i1 - 1      #10,2,1,0 순서로 앞 숫자와 비교(0부터 시작할 필요없음)
		cNum = array[i1]    #비교할 숫자
							 #내림차순 array[i2] < cNum
		while array[i2] > cNum and i2 >= 0:  # array[1]이 array[2]보다 크고 인덱스가 0보다 크면
			array[i2 + 1] = array[i2]        #array[2]자리에 array[1]
			i2 -= 1				   #array[0]까지 반복 -> 최종 -1    				

		array[i2+1] = cNum     #i2가 0까지 가면 -1이므로 +1

		print(f'{array}')    

print("before: ",array)
insertion_sort(array)
print("after:", array)


[5, 10, 2, 1, 0]
[5, 10, 10, 1, 0]
[5, 5, 10, 1, 0]     
[2, 5, 10, 1, 0]           #array[0] = 2

[정렬] 1부터 100사이 난수 정렬

---

 

🗝 선택정렬(Selection Sort)

- 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체.

- 각 회전 단계마다 다음으로 작은 값을 찾아서 이를 올바른 위치에 갖다 놓는다.

선택정렬 과정

import random

def selectNum(nums):

    for i in range(len(nums)-1):  # 0-3(맨 뒤까지 갈 필요 없음)
        minIdx = i
        for j in range(i+1, len(nums)): #1-4까지 비교
            if nums[minIdx] > nums[j]: #다른 인덱스의 값보다 크면
                minIdx = j         #최소값에 다른 값 넣어주기
        nums[i], nums[minIdx] = nums[minIdx], nums[i]  #최소값을 앞으로 보내기
        print(f'change : {nums}')
    return nums


array = random.sample(range(1,11), 5)
print(f'before : {array}')
result = selectNum(array)
print(f'after : {result}')


before : [10, 2, 9, 3, 7]
change : [2, 10, 9, 3, 7]
change : [2, 3, 9, 10, 7]
change : [2, 3, 7, 10, 9]
change : [2, 3, 7, 9, 10]
after : [2, 3, 7, 9, 10]

[정렬] 1-100 사이 난수 정렬

---

 

🗝 병합 정렬(Merge Sort)

- 리스트를 두 부분으로 쪼개서 작은 값부터 하나하나 병합하는 정렬 방법.

- 재귀함수를 이용해서 구현 가능. 데이터 크기만큼의 스택 메모리가 필요\

병합 정렬 과정

 

def mSort(arr):   # 분할
    if len(arr) < 2:
        return arr

    midIdx = len(arr) // 2 # 중간값을 구하고
 
    leftArr = mSort(arr[0:midIdx]) # 중간값을 기준으로 반만 재귀 호출(왼쪽)
    rightArr = mSort(arr[midIdx:len(arr)]) # 중간값을 기준으로 반만 재귀 호출(오른쪽)

    mergeArr = []
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftArr) and rightIdx < len(rightArr):  # 병합과정

        if leftArr[leftIdx] < rightArr[rightIdx]: # 자리바꿈
            mergeArr.append(leftArr[leftIdx])
            
            leftIdx += 1

        else:
            mergeArr.append(rightArr[rightIdx])
            rightIdx += 1


    mergeArr = mergeArr + leftArr[leftIdx:]
    mergeArr = mergeArr + rightArr[rightIdx:]

    return mergeArr

array = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'Array : {array}')
print(f'Merge Sort : {mSort(array)}')

--------------------------------------
Array : [8, 1, 4, 3, 2, 5, 10, 6]
Merge Sort : [1, 2, 3, 4, 5, 6, 8, 10]

[정렬] 1-100사이 난수 정렬(병합)

---

 

🗝 퀵 정렬(Quick Sort)

- 기준값보다 작은 값과 큰 값으로 분리한 후 합친다.

- 불안정 정렬이며, 상대적으로 빠른 정렬 방법.

- 데이터양이 N배 많이 진다면, 실행 시간은 N배 보다 조금 더 많아 진다(정비례 하지 않는다.)

- 재귀 함수를 통해 구현.

퀵 정렬 과정

import random

array = random.sample(range(1, 10), 5)

def qSort(arr):

    if len(arr) < 2:
        return arr

    midIdx = len(arr)//2

    midVal = arr[midIdx]

    smallArr = []; sameArr = []; bigArr = []

    for n in arr:
        if n < midVal:
            smallArr.append(n)

        elif n == midVal:
            sameArr.append(n)

        else:
            bigArr.append(n)

    return qSort(smallArr) + sameArr + qSort(bigArr)

print("before: ",array)
array = qSort(array)
print("after:", array)


--------------------------
before:  [5, 9, 3, 7, 6]
after: [3, 5, 6, 7, 9]

[정렬] 1부터 100사이 난수 정렬(퀵 정렬)

---

 

🗝 쉘정렬(Shell Sort)

- 불안정 정렬이며 삽입 정렬을 개선한 확장판. 적은량의 데이터에서 빠른 속도를 나타냄

- 일정한 방법으로 간격을 나누고 그 간격별로 삽입정렬을 실행하는 방법

import random 

array = random.sample(range(1, 10), 5) 

print(array) # 정렬 전 리스트
print('')

def InsertionSort(x, start, gap): # 삽입정렬 구현
    for target in range(start+gap, len(x), gap): # (시작인덱스+차이, 리스트 크기만큼 반복, 차이까지)
        val = x[target] # 리스트의 값
        i = target #  인덱스 저장
        while i > start: #  증감 값 보다 인덱스가 크다면 반복
            if x[i-gap] > val: # 리스트의 비교 인덱스 값 보다 크다면
                x[i] = x[i-gap] #  해당 인덱스 값 할당
            else: # 리스트의 비교 인덱스 값 보다 작다면
                break # 반복 중지
            i -= gap #  중간 값만큼 빼주기
        x[i] = val # 해당 값 삽입

def shellSort(x): #
    gap = len(x) // 2 # 리스트를 2로 나눈 몫 (중간 값) 취함
    while gap > 0: #
        for start in range(gap): # 중간 값의 크기만큼 반복
            InsertionSort(x, start, gap) # 삽입정렬 메소드 호출 (리스트, 증감 값, 중간 값)
        gap = gap // 2 # 리스트를 2로 나눈 몫 (중간 값) 취함 (반으로 줄여나간다.)
shellSort(array)

print('')
print(array) # 정렬 후 리스트

---

 

🗝 기수 정렬

- 시간 복잡도가 O(d(n+k))으로 선형 시간에 수행 할 수 있는 정렬 알고리즘

   (d: 자리 수를 의미, d 자리수 숫자 n개가 주어졌을 때, 각 자리 수에서 최대 k값을 가질 수 있다.)

- MSB->LSB(큰 자리 수부터 정렬), LSB->MSB(작은 자리수부터 정렬)하는 2가지 방식이 있다.

- 최대 O(dn)의 시간복잡도를 갖는다.

import random

array = random.sample(range(1,10),5)
print(array) # 정렬 전 리스트
print('')

def radixSort(a):
    isSort = False # 정렬 완료시 True
    index = 1 # 시작 인덱스
    while not isSort: # 정렬이 되지 않았다면 반복
        isSort = True # 정렬 상태 확인 변수
        sortList = [list()for _ in range(10)] # 빈 리스트 선언

        for num in a: # 리스트의 크기만큼 반복
            number = (int)(num/index)%10 # 자리 수를 기준으로 정렬하기 위한 변수 할당
            sortList[number].append(num) # 자리 수를 기준으로 리스트에 인덱스 선언
            if isSort and number > 0: # 정렬 되지 않았다면 && 자리 수 변수가 0보다 크다면
                isSort = False # 정렬 안 됨~

        i = 0 # 인덱스 증가용 변수 선언
        for number1 in sortList: # 정렬 리스트 크기만큼 반복
            for num in number1: # 증감 값의 크기만큼 반복
                a[i] = num # 리스트에 인덱스 값 넣기
                i += 1 # 인덱스 증가
        index *= 10 # 자리 수 증가
radixSort(array)

print('')
print(array) # 정렬 후 리스트

---

 

🗝 참고문헌

Sorting Algorithms in Python, realpython, 2022.5.5, URL:https://realpython.com/sorting-algorithms-python/

Sorting Algorithms in Python – Real Python

 

정렬 알고리즘 종류와 설명(파이썬 예제), sancho.log, 2022.5.4, URL:https://velog.io/@jguuun/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

정렬 알고리즘 종류와 설명(파이썬 예제)

 

파이썬을 이용한 정렬 알고리즘, 슈퍼문의 개발일지, 2022.5.4, URL:https://seongjaemoon.github.io/python/2017/12/16/pythonSort.html

슈퍼문의 개발일지