[알고리즘] 정렬 알고리즘

버블정렬

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

nums = [10, 2, 7, 21, 0]

length = len(nums) - 1

for i in range(len(nums)-1):
    for j in range(len(nums)-1-i):
        if nums[j] > nums[j+1]:
            temp = nums[j]
            nums[j] = nums[j+1]
            nums[j+1] = temp
        print(nums)
    print()
    
print(f'sorted nums: {nums}')

[연습문제]

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다.

• Modual

import copy

def bubbleSort(ns, deepCopy=True):

    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

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

    return cns

• 실행 파일

import sortMod as sm
import random as rd

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

sortedStudents = sm.bubbleSort(students)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

삽입정렬

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

import sortMod as sm
nums = [5, 10, 2, 1, 0]


# ascending
for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]

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

    nums[i2+1] = cNum

    print(f'nums: {nums}')


#descending
for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]

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

    nums[i2+1] = cNum

    print(f'nums: {nums}')

[연습문제]

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

• 요구 사항1) 생성된 난수들을 오름 차순 또는 내림 차순으로 정렬하는 알고리즘 구현
• 요구 사항2) 생성된 난수 중 최솟값, 최댓값을 반환하는 함수 구현
• Modual

class SortNumbers:

    def __init__(self, ns, asc=True):
        self.nums = ns
        self.isAsc = asc

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

    def setSort(self):

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

            if self.isAsc:
                while self.nums[i2] > cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
            else:
                while self.nums[i2] < cNum and i2 >= 0:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

            self.nums[i2 + 1] = cNum

    def getSortedNumbers(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 self.isAsc:
            return self.nums[len(self.nums)-1]
        else:
            return self.nums[0]

• 실행 파일

import random
import sortMod as sm

nums = random.sample(range(1, 1000), 100)
print(f'not sortedNumber: {nums}')

# 객체 생성
sn = sm.SortNumbers(nums)

# ascending
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by ASC: {sortedNumber}')

# descending
sn.isAscending(False)
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by DESC: {sortedNumber}')

# min & max
print(f'MinNumber : {sn.getMinNumber()}')
print(f'MaxNumber : {sn.getMaxNumber()}')

선택정렬

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

[연습문제]

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

• Modual

def sortNumber(ns, asc=True):

    cnt = 0

    for i in range(len(ns) - 1):
        targetIdx = i

        for j in range(i + 1, len(ns)):
            if asc:
                if ns[targetIdx] > ns[j]:
                    targetIdx = j
                    cnt += 1
            else:
                if ns[targetIdx] < ns[j]:
                    targetIdx = j
                    cnt += 1

        ns[i], ns[targetIdx] = ns[targetIdx], ns[i]

    print(f'cnt: {cnt}')

    return ns

import random
import sortMod as sm

scores = random.sample(range(50, 101), 20)
print(f'scores: {scores}')
print(f'scores length: {len(scores)}')

# ascending
result = sm.sortNumber(scores)
print(f'result(ASC): {result}')

# descending
result = sm.sortNumber(scores, asc=False)
print(f'result(DESC): {result}')

병합정렬

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

def mSort(ns):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx])
    rightNums = mSort(ns[midIdx:len(ns)])

    mergedNums = []
    leftIdx = 0; rightIdx = 0
    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergedNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergedNums.append(rightNums[rightIdx])
            rightIdx += 1

    mergedNums = mergedNums + leftNums[leftIdx:]
    mergedNums = mergedNums + rightNums[rightIdx:]
    print(f'mergedNums: {mergedNums}')
    return mergedNums


nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mSort(nums)}')

[연습문제]

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

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

def mSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

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

        if asc:

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

        else:

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

    mergedNums = mergedNums + leftNums[leftIdx:]
    mergedNums = mergedNums + rightNums[rightIdx:]
    return mergedNums

• 실행파일

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print(f'not sorted rNums: {sm.mSort(rNums)}')
print(f'merge sorted rNums by ASC: {sm.mSort(rNums)}')
print(f'merge sorted rNums by DESC: {sm.mSort(rNums, asc=False)}')

퀵정렬

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

def qSort(ns):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

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


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

    return qSort(smallNums) + sameNums + qSort(bigNums)


nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))

[연습문제]

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

• 요구 사항1) 퀵정렬 알고리즘을 이용한 난수 정렬 모듈 구현
• 요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가
• Modual

def qSort(ns, asc=True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

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


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

    if asc:
        return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

• 실행파일

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)

print(f'not sorted rNums: {sm.qSort(rNums)}')
print(f'merge sorted rNums by ASC: {sm.qSort(rNums)}')
print(f'merge sorted rNums by DESC: {sm.qSort(rNums, asc=False)}')