[Python][알고리즘][정렬] : 버블, 삽입, 선택, 병합, 퀵

·2023년 3월 23일
0
post-thumbnail

✒️ 버블정렬 이란?

처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘


nums = [10, 2, 7, 21, 0]
print(f'not sorted nums : {nums}')

length = len(nums) - 1
for i in range(length):
    for j in range(length-i):
        if nums[j] > nums[j + 1]:
            # temp = nums[j]
            # nums[j] = nums[j + 1]
            # nums[j + 1] = temp
            nums[j], nums[j + 1] = nums[j + 1], nums[j]

print(f'sorted nums : {nums}')
not sorted nums : [10, 2, 7, 21, 0]
sorted nums : [0, 2, 7, 10, 21]

✍️실습

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄세워보자


nums = [10, 2, 7, 21, 0]
print(f'not sorted nums : {nums}')

length = len(nums) - 1
for i in range(length):
    for j in range(length-i):
        if nums[j] > nums[j + 1]:
            # temp = nums[j]
            # nums[j] = nums[j + 1]
            # nums[j + 1] = temp
            nums[j], nums[j + 1] = nums[j + 1], nums[j]

print(f'sorted nums : {nums}')
not sorted nums : [10, 2, 7, 21, 0]
sorted nums : [0, 2, 7, 10, 21]

✒️ 삽입정렬 이란?

정렬되어 있는 자료배열과 비교해서, 정렬 위치를 찾는다

# 삽입 정렬
nums = [5, 10, 2, 1, 0, 7, 8]

# ASCENDING
for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]
    print(f'ASC {i1} nums : {nums}')

    while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 + 1] = cNum

# print(f'nums : {nums}')

# 삽입 정렬
# DESCENDING
nums = [5, 10, 2, 1, 0, 7, 8]

length = len(nums)
for i1 in range(1, length):
    i2 = i1 - 1
    num = nums[i1]
    print(f'DES {i1} nums : {nums}')

    while i2 >= 0 and nums[i2] < num:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 + 1] = num

ASC 1 nums : [5, 10, 2, 1, 0, 7, 8]
ASC 2 nums : [5, 10, 2, 1, 0, 7, 8]
ASC 3 nums : [2, 5, 10, 1, 0, 7, 8]
ASC 4 nums : [1, 2, 5, 10, 0, 7, 8]
ASC 5 nums : [0, 1, 2, 5, 10, 7, 8]
ASC 6 nums : [0, 1, 2, 5, 7, 10, 8]
DES 1 nums : [5, 10, 2, 1, 0, 7, 8]
DES 2 nums : [10, 5, 2, 1, 0, 7, 8]
DES 3 nums : [10, 5, 2, 1, 0, 7, 8]
DES 4 nums : [10, 5, 2, 1, 0, 7, 8]
DES 5 nums : [10, 5, 2, 1, 0, 7, 8]
DES 6 nums : [10, 7, 5, 2, 1, 0, 8]

✍️실습

1부터 1000까지의 난수 100개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자

  1. 생성된 난수들은 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현
  2. 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
#class SortNumbers

class SortNumbers:
    def __init__(self, nums, asc=True, isCopy=True):
        if isCopy:
            self.nums = copy.copy(nums)
        else:
            self.nums = nums
        self.isAsc = asc

    def isAscending(self, flag):
        self.isAsc = flag

    # 삽입 졍렬 사용
    def setSort(self):
        length = len(self.nums)

        for i1 in range(1, length):
            i2 = i1 - 1
            value = self.nums[i1]

            # Ascending
            if self.isAsc:
                while i2 >= 0 and value < self.nums[i2]:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

                self.nums[i2 + 1] = value

            # Descending
            else:
                while i2 >= 0 and value > self.nums[i2]:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

                self.nums[i2 + 1] = value

    def getSortNumber(self):
        return self.nums

    def getMinNumber(self):
        if self.isAsc:
            return self.nums[0]
        else:
            return self.nums[len(self.nums) - 1]

    def getMaxNumber(self):
        if not self.isAsc:
            return self.nums[0]
        else:
            return self.nums[len(self.nums) - 1]

# 1부터 1000까지의 난수 100개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 생성된 난수들은 오름차순 또는 내림차순으로 정렬하는 알고리즘 구현
# 2. 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
import random
from module import sortMod

nums = random.sample(range(1, 1001), 100)
sortNum = sortMod.SortNumbers(nums)

print(f'정렬 전 \t\t : {nums}')
sortNum.setSort()
print(f'정렬 후 \t\t : {sortNum.getSortNumber()}')
print(f'가장 큰 수 \t : {sortNum.getMaxNumber()}')
print(f'가장 작은 수 \t : {sortNum.getMinNumber()}')
print(f'원본 \t\t : {nums}')

정렬 전 		 : [744, 360, 610, 528, 586, 193, 350, 976, 706, 966, 845, 618, 915, 333, 993, 775, 644, 221, 964, 973, 857, 420, 944, 189, 653, 224, 743, 271, 756, 12, 93, 43, 986, 284, 541, 689, 599, 642, 361, 711, 52, 593, 537, 45, 236, 903, 843, 524, 72, 159, 370, 55, 935, 504, 764, 375, 635, 409, 321, 708, 844, 829, 446, 842, 244, 503, 754, 100, 848, 395, 228, 548, 103, 33, 112, 194, 981, 606, 154, 822, 8, 423, 274, 95, 611, 555, 270, 921, 336, 959, 647, 725, 117, 253, 17, 184, 726, 913, 471, 691]
정렬 후 		 : [8, 12, 17, 33, 43, 45, 52, 55, 72, 93, 95, 100, 103, 112, 117, 154, 159, 184, 189, 193, 194, 221, 224, 228, 236, 244, 253, 270, 271, 274, 284, 321, 333, 336, 350, 360, 361, 370, 375, 395, 409, 420, 423, 446, 471, 503, 504, 524, 528, 537, 541, 548, 555, 586, 593, 599, 606, 610, 611, 618, 635, 642, 644, 647, 653, 689, 691, 706, 708, 711, 725, 726, 743, 744, 754, 756, 764, 775, 822, 829, 842, 843, 844, 845, 848, 857, 903, 913, 915, 921, 935, 944, 959, 964, 966, 973, 976, 981, 986, 993]
가장 큰 수 	 : 993
가장 작은 수 	 : 8
원본 		 : [744, 360, 610, 528, 586, 193, 350, 976, 706, 966, 845, 618, 915, 333, 993, 775, 644, 221, 964, 973, 857, 420, 944, 189, 653, 224, 743, 271, 756, 12, 93, 43, 986, 284, 541, 689, 599, 642, 361, 711, 52, 593, 537, 45, 236, 903, 843, 524, 72, 159, 370, 55, 935, 504, 764, 375, 635, 409, 321, 708, 844, 829, 446, 842, 244, 503, 754, 100, 848, 395, 228, 548, 103, 33, 112, 194, 981, 606, 154, 822, 8, 423, 274, 95, 611, 555, 270, 921, 336, 959, 647, 725, 117, 253, 17, 184, 726, 913, 471, 691]

✒️ 선택정렬 이란?

주어진 리스트 중에 최솟값을 찾아, 그 값을 맨앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘


nums = [4, 2, 5, 1, 3]
print(nums)
for i in range(len(nums) - 1):
    temp1 = i
    for j in range(i + 1, len(nums)):
        if nums[temp1] > nums[j]:
            temp1 = j

    nums[i], nums[temp1] = nums[temp1], nums[i]
    print(nums)
[4, 2, 5, 1, 3]
[1, 2, 5, 4, 3]
[1, 2, 5, 4, 3]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

✍️실습

선택정렬 알고리즘을 이용해서 학생 20명의 시험점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험점수는 50부터 100까지로 한다.

# class SelectSort
class SelectSort:

    def __init__(self, scores, isAsc=True):
        self.scores = scores
        self.isAsc = isAsc

    def setSortScore(self):
        for i in range(len(self.scores) - 1):
            idx = i
            for j in range(i + 1, len(self.scores)):
                if self.isAsc:
                    if self.scores[idx] > self.scores[j]:
                        idx = j
                else:
                    if self.scores[idx] < self.scores[j]:
                        idx = j

            self.scores[i], self.scores[idx] = self.scores[idx], self.scores[i]

    def getSortScore(self):
        return self.scores

    def setIsAsc(self, isAsc):
        self.isAsc = isAsc

    def printScore(self):
        if self.isAsc:
            print(f'[ASC] sorted scores \t: {self.scores}')
        else:
            print(f'[DES] sorted scores \t: {self.scores}')
import random

from module import sortMod

scores = random.sample(range(50, 101), 20)
print(f'not sorted scores \t\t: {scores}  ')
sort = sortMod.SelectSort(scores)
sort.setSortScore()
sort.printScore()
not sorted scores 		: [73, 99, 87, 77, 86, 59, 70, 52, 63, 80, 78, 90, 50, 92, 62, 69, 54, 81, 51, 61]  
[ASC] sorted scores 	: [50, 51, 52, 54, 59, 61, 62, 63, 69, 70, 73, 77, 78, 80, 81, 86, 87, 90, 92, 99]

not sorted scores 		: [60, 96, 83, 52, 86, 75, 51, 70, 50, 97, 84, 82, 85, 95, 67, 77, 92, 81, 62, 54]  
[DES] sorted scores 	: [97, 96, 95, 92, 86, 85, 84, 83, 82, 81, 77, 75, 70, 67, 62, 60, 54, 52, 51, 50]

✒️ 병합정렬 이란?

자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬

# 병합정렬

def mergeSort(nums):
    if len(nums) < 2:
        return nums

    miIdx = len(nums) // 2
    leftNums = mergeSort(nums[:miIdx])
    rightNums = mergeSort(nums[miIdx:])

    mergeNums = []
    leftIdx = 0
    rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]
    print(mergeNums)

    return mergeNums


nums = [7, 3, 2, 16, 24, 4, 11, 9]
mergeSort(nums)
[3, 7]
[2, 16]
[2, 3, 7, 16]
[4, 24]
[9, 11]
[4, 9, 11, 24]
[2, 3, 4, 7, 9, 11, 16, 24]

✍️실습

1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자

  1. 병합정렬 알고리즘을 이용한 난수 모듈 구현
  2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
# 병합 모듈

def setMergeSort(nums, isAsc=True):
    if len(nums) < 2:
        return nums
    # 분할 단계
    midIdx = len(nums) // 2
    leftNums = setMergeSort(nums[:midIdx], isAsc)
    rightNums = setMergeSort(nums[midIdx:], isAsc)

    # 병합 단계
    mergeNums = []
    leftIdx = 0
    rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if isAsc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

    if isAsc:
        print(f'ASC mergeNums \t: {mergeNums}')
    else:
        print(f'DES mergeNums \t: {mergeNums}')

    return mergeNums
# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 병합정렬 알고리즘을 이용한 난수 모듈 구현
# 2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
import copy
import random
from module import mergeMod

randoms = random.sample(range(1, 101), 10)
ascNums = copy.deepcopy(randoms)
desNums = copy.deepcopy(randoms)
print(f'not sored \t\t: {randoms}')
print('-'*60)
mergeMod.setMergeSort(ascNums, True)
print('-'*60)
mergeMod.setMergeSort(desNums, False)
not sored 		: [61, 4, 80, 30, 67, 18, 40, 56, 43, 57]
------------------------------------------------------------
ASC mergeNums 	: [4, 61]
ASC mergeNums 	: [30, 67]
ASC mergeNums 	: [30, 67, 80]
ASC mergeNums 	: [4, 30, 61, 67, 80]
ASC mergeNums 	: [18, 40]
ASC mergeNums 	: [43, 57]
ASC mergeNums 	: [43, 56, 57]
ASC mergeNums 	: [18, 40, 43, 56, 57]
ASC mergeNums 	: [4, 18, 30, 40, 43, 56, 57, 61, 67, 80]
------------------------------------------------------------
DES mergeNums 	: [61, 4]
DES mergeNums 	: [67, 30]
DES mergeNums 	: [80, 67, 30]
DES mergeNums 	: [80, 67, 61, 30, 4]
DES mergeNums 	: [40, 18]
DES mergeNums 	: [57, 43]
DES mergeNums 	: [57, 56, 43]
DES mergeNums 	: [57, 56, 43, 40, 18]
DES mergeNums 	: [80, 67, 61, 57, 56, 43, 40, 30, 18, 4]

✒️ 퀵정렬 이란?

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


# 퀵 정렬
def qSort(nums):
    if len(nums) < 2:
        return nums

    pivotIdx = len(nums) // 2
    pivotValue = nums[pivotIdx]

    smallNums, sameNums, bigNums = [], [], []

    for n in nums:
        if n < pivotValue:
            smallNums.append(n)
        elif n == pivotValue:
            sameNums.append(n)
        else:
            bigNums.append(n)

    print('-' * 40)
    print(f'nums\t: {nums}')
    if len(smallNums) > 0 or len(bigNums) > 0:
        print('-' * 40)
        print(f'small\t: {smallNums}\npivot\t: {sameNums}\nbig\t\t: {bigNums}')
    return qSort(smallNums) + sameNums + qSort(bigNums)


nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(f'{qSort(nums)}')
nums	: [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
----------------------------------------
small	: [1, 4, 3, 2, 4]
pivot	: [5]
big		: [8, 10, 6, 8]
----------------------------------------
nums	: [1, 4, 3, 2, 4]
----------------------------------------
small	: [1, 2]
pivot	: [3]
big		: [4, 4]
----------------------------------------
nums	: [1, 2]
----------------------------------------
small	: [1]
pivot	: [2]
big		: []
----------------------------------------
nums	: [4, 4]
----------------------------------------
nums	: [8, 10, 6, 8]
----------------------------------------
small	: []
pivot	: [6]
big		: [8, 10, 8]
----------------------------------------
nums	: [8, 10, 8]
----------------------------------------
small	: [8, 8]
pivot	: [10]
big		: []
----------------------------------------
nums	: [8, 8]
[1, 2, 3, 4, 4, 5, 6, 8, 8, 10]

✍️실습

1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자

  1. 퀵 정렬 알고리즘을 이용한 난수 모듈 구현
  2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
# 퀵 정렬
def setQuickSort(nums, isAsc=True):
    if len(nums) < 2:
        return nums

    smallList, sameList, bigList = [], [], []
    pivotIdx = len(nums) // 2
    pivotVal = nums[pivotIdx]

    for n in nums:
        if n > pivotVal:
            bigList.append(n)
        elif n == pivotVal:
            sameList.append(n)
        else:
            smallList.append(n)

    if isAsc:
        return setQuickSort(smallList, isAsc) + sameList + setQuickSort(bigList, isAsc)
    else:
        return setQuickSort(bigList, isAsc) + sameList + setQuickSort(smallList, isAsc)

# 1부터 100까지의 난수 10개를 생성하고, 다음의 요구사항을 만족하는 모듈을 만들어보자
# 1. 병합정렬 알고리즘을 이용한 난수 모듈 구현
# 2. 위의 모듈에 오름차순과 내림차순 선택할 수 있는 옵션 추가
import copy
import random
from module import mergeMod

randoms = random.sample(range(1, 101), 10)
ascNums = copy.deepcopy(randoms)
desNums = copy.deepcopy(randoms)
print(f'not sored \t\t: {randoms}')
print('-'*60)
mergeMod.setMergeSort(ascNums, True)
print('-'*60)
mergeMod.setMergeSort(desNums, False)
randoms : [66, 91, 89, 99, 22, 37, 93, 8, 51, 6]
ASC		: [6, 8, 22, 37, 51, 66, 89, 91, 93, 99]
DES		: [99, 93, 91, 89, 66, 51, 37, 22, 8, 6]



자료구조+알고리즘 후기
자료구조는 그 동안 문제풀이에서 사용해 본 리스트 타입을 응용해보는 느낌이라면 자료구조는 알고있던 개념이지만 코드로 구현하니 아예 새롭게 느껴진다. 특히, 병합 정렬은 구현하기에 많은 시간이 걸렸다. 알고리즘은 문제를 해결할 때 가의 필수로 사용되는 개념이기 때문에 이번 강의를 통해 확실히 구분해둘 필요를 느꼈다.
profile
개발하고싶은사람

0개의 댓글