정렬 기본

정렬:

자료들을 일정한 순서대로 나열하는 것

 

선택 정렬:

여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬

 

삽입 정렬:

기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬 방법

 

최솟값을 찾는 방법:
    1. 배열의 첫번째 값을 가장 작은 값으로 지정
    2. 가장 작은 값으로 지정한 값을 다음 차례의 값과 비교하여 가장 작은 값을 변경하거나 그대로 두기
    3. 마지막 값까지 비교를 마친 후 현재 가장 작은 값으로 지정된 값을 가장 작은 값으로 결정

 

#배열에서 최소값 위치를 찾는 함수
def findMinIdx(ary) :
    minIdx = 0
    for i in range(1, len(ary)) :       #배열의 두번째 칸부터 반복
        if (ary[minIdx] > ary[i]) :     #배열의 i번째 값과 현재  최솟갑을 비교해서 i뻔째 값이 현재 최솟값보다 작다면 i를 현재 최솟값으로 지정한다.
            minIdx = i
        return minIdx                   #찾아낸 배열의 최솟값 위치를 반환

testAry = [55, 88, 33, 77]
minPos = findMinIdx(testAry)
print('최솟값 -->', testAry[minPos])

최솟값 --> 55

 

#가변 크기의 배열 추가
ary = []
ary.append(100)
ary.append(200)
ary.append(300)

 

#선택 정렬 구현
#클래스와 함수 선언 부분
def findMinIdx(ary) :
    minIdx = 0
    for i in range(1, len(ary)) :       #배열의 두번째 칸부터 반복
        if (ary[minIdx] > ary[i]) :     #배열의 i번째 값과 현재  최솟갑을 비교해서 i뻔째 값이 현재 최솟값보다 작다면 i를 현재 최솟값으로 지정한다.
            minIdx = i
    return minIdx                       #찾아낸 배열의 최솟값 위치를 반환

#전역 변수 선언 부분
before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

#전역 변수 선언 부분
print('정렬 전-->', before)
for _ in range(len(before)) :
    minPos = findMinIdx(before)
    after.append(before[minPos])
    del(before[minPos])
print('정렬 후 -->', after)

정렬 전--> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

#개선된 선택 정렬 구현
def selectionSort(ary) :
    n = len(ary)
    for i in range(0, n-1) :
        minIdx = i
        for k in range(i+1, n) :
            if (ary[minIdx] > ary[k]) :
                minIdx = k
            tmp = ary[i]
            ary[i] = ary[minIdx]
            ary[minIdx] = tmp

    return ary

#전역변수 선언 부분
dataAry = [188, 162, 168, 120, 50, 150, 177, 105]


#메인 코드 부분
print('정렬 전 -->', datAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

 

삽입 정렬 :
    기존 데이터 중에 자신의 위치를 찾아 데이터를 삽입하는 정렬 방법

 

#배열에서 자신이 삽입될 위치를 찾는 함수
def findInsertIdx(ary, data) :
    findIdx = -1
    for i in range(0, len(ary)) :
        if (ary[i] > data) :
            findIdx = i
            break
    if findIdx == -1 :
        return len(ary)
    else :
        return findIdx

testAry = []
insPos = findInsertIdx(testAry, 55)
print('삽입할 위치 -->', insPos)

testAry = [33, 77, 88]
insPos = findInsertIdx(testAry, 55)
print('삽입할 위치 -->', insPos)

testAry = [33, 55, 77, 88]
insPos = findInsertIdx(testAry, 100)
print('삽입할 위치 -->', insPos)

삽입할 위치 --> 0
삽입할 위치 --> 1
삽입할 위치 --> 4

 

#함수 선언 부분
#배열에서 자신이 삽입될 위치를 찾는 함수
def findInsertIdx(ary, data) :
    findIdx = -1
    for i in range(0, len(ary)) :
        if (ary[i] > data) :
            findIdx = i
            break
    if findIdx == -1 :
        return len(ary)
    else :
        return findIdx

#전역 변수 부분
before = [188, 162, 168, 120, 50, 150,177, 105]
after = []

#메인 코드 부분
print('정렬 전 -->', before)
for i in range(len(before)) :
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)

print('정렬 후 -->', after)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]

 

#삽입 정렬의 효율적인 구현
#함수 선언 부분
def insertionSort(ary) :
    n = len(ary)
    for end in range(1, n) :
        for cur in range(end, 0, -1) :
            if(ary[cur-1] > ary[cur]) :
                ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
    return ary

#전역 변수 선언 부분
dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

#메인 코드 부분
print('정렬 전 -->', dataAry)
dataAry = insertionSort(dataAry)
print('정렬 후 -->', dataAry)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 105]
정렬 후 --> [50, 105, 120, 150, 162, 168, 177, 188]