삽입 정렬(Insertion Sort) (파이썬)

 

 

 

삽입 정렬

---

 

 

 

 

삽입 정렬(Insertion Sort)

삽입 정렬은 두 번째 인덱스부터 시작합니다. 
해당 인덱스(key 값) 앞에 있는 데이터부터 비교해서, key 값이 더 작으면 그 데이터 값을 뒤 인덱스로 복사한다
이를 key 값이 더 큰 데이터를 만날 때까지 반복하고 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동

즉 n번째 인자를 그 이전의 인자와 비교를 하고 순서를 바꿈으로써 순서를 맞추는 것이 삽입 정렬의 기본 원리이자 핵심이다. 

 

 

 

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

nums = [5, 10, 2, 1, 0]
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}')

nums: [5, 10, 2, 1, 0]
nums: [2, 5, 10, 1, 0]
nums: [1, 2, 5, 10, 0]
nums: [0, 1, 2, 5, 10]

import sortMod as sm
nums = [5, 10, 2, 1, 0]
result = sm.sortNumber(nums, asc=False)
print(f'result: {result}')

result: [10, 5, 2, 1, 0]

nums = [0, 5, 2, 10, 1]

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}')

nums: [5, 0, 2, 10, 1]
nums: [5, 2, 0, 10, 1]
nums: [10, 5, 2, 0, 1]
nums: [10, 5, 2, 1, 0]

 

 

 

[9, 3, 2, 5]의 리스트를 삽입 정렬의 순서로 나타내면, 

 

1회 실행: key 값은 9 -> 인덱스(0)이므로 앞의 인자가 없음. 따라서 그대로 종료. [9, 3, 2, 5]

2회 실행: key 값은 3 -> 인덱스(1)이므로 앞의 인자 9와 비교를 진행 및 순서 교체. [3, 9, 2, 5]

3회 실행: key 값은 2 -> 인덱스(2)이므로 앞의 인자 3,9 와 비교를 진행 및 순서 교체. [2, 3, 9, 5]

4회 실행: key 값은 5 -> 인덱스(3)이므로 앞의 모든 인자와 비교를 지행 및 순서 교체. [2, 3, 5, 9]

 

 

 

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

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()}')

def sortNumber(ns, asc=True):

    if asc:
        for i1 in range(1, len(ns)):
            i2 = i1 - 1
            cNum = ns[i1]

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

            ns[i2+1] = cNum
    else:
        for i1 in range(1, len(ns)):
            i2 = i1 - 1
            cNum = ns[i1]

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

            ns[i2 + 1] = cNum

    return ns

not sortedNumber: [39, 83, 203, 296, 429, 894, 193, 776, 220, 48, 863, 982, 359, 814, 49, 634, 947, 111, 69, 505, 242, 957, 132, 139, 969, 272, 427, 888, 481, 672, 893, 586, 723, 136, 880, 299, 292, 85, 970, 783, 987, 621, 897, 387, 301, 335, 245, 747, 577, 890, 956, 285, 812, 885, 483, 305, 118, 671, 977, 871, 813, 555, 746, 722, 720, 414, 247, 704, 227, 997, 531, 275, 659, 795, 348, 696, 668, 300, 87, 994, 699, 992, 727, 426, 390, 190, 985, 850, 130, 945, 249, 662, 651, 591, 413, 386, 407, 830, 312, 639]
sortedNumber by ASC: [39, 48, 49, 69, 83, 85, 87, 111, 118, 130, 132, 136, 139, 190, 193, 203, 220, 227, 242, 245, 247, 249, 272, 275, 285, 292, 296, 299, 300, 301, 305, 312, 335, 348, 359, 386, 387, 390, 407, 413, 414, 426, 427, 429, 481, 483, 505, 531, 555, 577, 586, 591, 621, 634, 639, 651, 659, 662, 668, 671, 672, 696, 699, 704, 720, 722, 723, 727, 746, 747, 776, 783, 795, 812, 813, 814, 830, 850, 863, 871, 880, 885, 888, 890, 893, 894, 897, 945, 947, 956, 957, 969, 970, 977, 982, 985, 987, 992, 994, 997]
sortedNumber by DESC: [997, 994, 992, 987, 985, 982, 977, 970, 969, 957, 956, 947, 945, 897, 894, 893, 890, 888, 885, 880, 871, 863, 850, 830, 814, 813, 812, 795, 783, 776, 747, 746, 727, 723, 722, 720, 704, 699, 696, 672, 671, 668, 662, 659, 651, 639, 634, 621, 591, 586, 577, 555, 531, 505, 483, 481, 429, 427, 426, 414, 413, 407, 390, 387, 386, 359, 348, 335, 312, 305, 301, 300, 299, 296, 292, 285, 275, 272, 249, 247, 245, 242, 227, 220, 203, 193, 190, 139, 136, 132, 130, 118, 111, 87, 85, 83, 69, 49, 48, 39]
MinNumber : 39
MaxNumber : 997