Ch11 Lab - 정렬 (기본)

Code11-01.py

배열에서 최솟값의 위치를 찾습니다

def findMinIdx(ary) :

	minIdx = 0
	for i in range(1, len(ary)) :
		if (ary[minIdx] > ary[i] ) :
			minIdx = i
	return minIdx

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

Code11-01.py

Finds the index of the minimum value in an array

def findMinIdx(ary) :

	minIdx = 0
	for i in range(1, len(ary)) :
		if (ary[minIdx] > ary[i] ) :
			minIdx = i
	return minIdx

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

Code11-02.py

최솟값 위치를 이용해 두 값을 교환합니다

## 함수 선언 부분 ##
def findMinIdx(ary) :

	minIdx = 0
	for i in range(1, len(ary)) :
		if (ary[minIdx] > ary[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)

Code11-02.py

Swaps two values using the minimum index

## Function Declarations ##
def findMinIdx(ary) :

	minIdx = 0
	for i in range(1, len(ary)) :
		if (ary[minIdx] > ary[i]) :
			minIdx = i
	return minIdx

## Global Variables ##
before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

## Main Code ##
print('Before sorting -->', before)
for _ in range(len(before)) :
	minPos = findMinIdx(before)
	after.append(before[minPos])
	del(before[minPos])
print('After sorting -->', after)

Code11-03.py

선택 정렬 알고리즘을 구현합니다

## 함수 선언 부분 ##
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('정렬 전 -->', dataAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

Code11-03.py

Implements the selection sort algorithm

## Function Declarations ##
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

## Global Variables ##
dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

## Main Code ##
print('Before sorting -->', dataAry)
dataAry = selectionSort(dataAry)
print('After sorting -->', dataAry)

Code11-04.py

삽입할 위치를 찾는 함수를 구현합니다

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)

Code11-04.py

Implements a function to find the insertion position

def findInsertIdx(ary, data) :

	findIdx = -1			# Initial value set to invalid position
	for i in range(0, len(ary)) :
		if (ary[i] > data ) :
			findIdx = i
			break
	if findIdx == -1 :			# No larger value found == last position
		return len(ary)
	else :
		return findIdx

testAry = []
insPos = findInsertIdx(testAry, 55)
print('Insert position -->' , insPos)

testAry = [33, 77, 88]
insPos = findInsertIdx(testAry, 55)
print('Insert position -->' , insPos)

testAry = [33, 55, 77, 88]
insPos = findInsertIdx(testAry, 100)
print('Insert position -->' , insPos)

Code11-05.py

삽입 정렬의 이동 과정을 확인합니다

## 함수 선언 부분 ##
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)

Code11-05.py

Demonstrates the shifting process of insertion sort

## Function Declarations ##
def findInsertIdx(ary, data) :

	findIdx = -1			# Initial value set to invalid position
	for i in range(0, len(ary)) :
		if (ary[i] > data ) :
			findIdx = i
			break
	if findIdx == -1 :			# No larger value found == last position
		return len(ary)
	else :
		return findIdx

## Global Variables ##
before = [188, 162, 168, 120, 50, 150, 177, 105]
after = []

## Main Code ##
print('Before sorting -->', before)
for i in range(len(before)) :
	data = before[i]
	insPos = findInsertIdx(after, data)
	after.insert(insPos, data)
print('After sorting -->', after)

Code11-06.py

삽입 정렬 알고리즘을 구현합니다

## 함수 선언 부분 ##
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)

Code11-06.py

Implements the insertion sort algorithm

## Function Declarations ##
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

## Global Variables ##
dataAry = [188, 162, 168, 120, 50, 150, 177, 105]

## Main Code ##
print('Before sorting -->', dataAry)
dataAry = insertionSort(dataAry)
print('After sorting -->', dataAry)

Code11-07.py

선택 정렬과 삽입 정렬의 성능을 비교합니다

## 함수 선언 부분 ##
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

## 전역 변수 선언 부분 ##
moneyAry = [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]

## 메인 코드 부분 ##

print('용돈 정렬 전 -->', moneyAry)
moneyAry = selectionSort(moneyAry)
print('용돈 정렬 후 -->', moneyAry)
print('용돈 중앙값 --> ', moneyAry[len(moneyAry)//2])

Code11-07.py

Compares performance of selection sort and insertion sort

## Function Declarations ##
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

## Global Variables ##
moneyAry = [7, 5, 11, 6, 9, 80000, 10, 6, 15, 12]

## Main Code ##
print('Allowance Before sorting -->', moneyAry)
moneyAry = selectionSort(moneyAry)
print('Allowance After sorting -->', moneyAry)
print('Allowance median --> ', moneyAry[len(moneyAry)//2])

Code11-08.py

파일 목록을 정렬하는 프로그램입니다

import os

## 함수 선언 부분 ##
def makeFileList(folderName) :

	fnameAry = []
	for dirName, subDirList, fnames in os.walk(folderName):
		for fname in fnames:
			fnameAry.append(fname)
	return fnameAry

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

## 전역 변수 선언 부분 ##
fileAry = []

## 메인 코드 부분 ##

fileAry = makeFileList('C:/Program Files/Common Files')
fileAry = insertionSort(fileAry)
print('파일명 역순 정렬 -->', fileAry)

Code11-08.py

Sorts a list of files using sorting algorithms

import os

## Function Declarations ##
def makeFileList(folderName) :

	fnameAry = []
	for dirName, subDirList, fnames in os.walk(folderName):
		for fname in fnames:
			fnameAry.append(fname)
	return fnameAry

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

## Global Variables ##
fileAry = []

## Main Code ##
fileAry = makeFileList('C:/Program Files/Common Files')
fileAry = insertionSort(fileAry)
print('Sort filenames in reverse -->', fileAry)

EX11-02.py

정렬 응용: 선택 정렬 심화 실습

## 함수 선언 부분 ##
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

## 전역 변수 선언 부분 ##
ary2 = [[55, 33, 250, 44],
		 [88,  1,  67, 23],
		 [199,222, 38, 47],
		 [155,145, 20, 99]]
ary1 = []

## 메인 코드 부분 ##

for i in range(len(ary2)) :
	for k in range(len(ary2[i])) :
		ary1.append(ary2[i][k])

print('1차원 변경 후, 정렬 전 -->', ary1)
ary1 = selectionSort(ary1)
print('1차원 변경 후, 정렬 후 -->', ary1)
print('중앙값 --> ', ary1[len(ary1)//2])

EX11-02.py

Sorting application: advanced selection sort practice

## Function Declarations ##
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

## Global Variables ##
ary2 = [[55, 33, 250, 44],
		 [88,  1,  67, 23],
		 [199,222, 38, 47],
		 [155,145, 20, 99]]
ary1 = []

## Main Code ##
for i in range(len(ary2)) :
	for k in range(len(ary2[i])) :
		ary1.append(ary2[i][k])

print('After 1D conversion, before sorting -->', ary1)
ary1 = selectionSort(ary1)
print('After 1D conversion, after sorting -->', ary1)
print('Median --> ', ary1[len(ary1)//2])

Ex11-01.py

정렬 응용: 점수 기반 삽입 정렬

## 함수 선언 부분 ##
def scoreSort(ary) :

	n = len(ary)
	for end in range(1, n) :
		for cur in range(end, 0, -1) :
			if ( ary[cur-1][1] > ary[cur][1] ) :
				ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
	return ary

## 전역 변수 선언 부분 ##
scoreAry = [['선미', 88], ['초아', 99], ['화사', 71], ['영탁', 78], ['영웅', 67], ['민호', 92]]

## 메인 코드 부분 ##

print('정렬 전 -->', scoreAry)
scoreAry = scoreSort(scoreAry)
print('정렬 후 -->', scoreAry)

print('## 성적별 조 편성표 ##')
for i in range(len(scoreAry)//2) :
	print(scoreAry[i][0], ':' , scoreAry[len(scoreAry)-1-i][0])

Ex11-01.py

Sorting application: insertion sort by score

## Function Declarations ##
def scoreSort(ary) :

	n = len(ary)
	for end in range(1, n) :
		for cur in range(end, 0, -1) :
			if ( ary[cur-1][1] > ary[cur][1] ) :
				ary[cur-1], ary[cur] = ary[cur], ary[cur-1]
	return ary

## Global Variables ##
scoreAry = [['Sunmi', 88], ['Choa', 99], ['Hwasa', 71], ['YoungTak', 78], ['Hero', 67], ['Minho', 92]]

## Main Code ##
print('Before sorting -->', scoreAry)
scoreAry = scoreSort(scoreAry)
print('After sorting -->', scoreAry)

print('## Team assignments by grade ##')
for i in range(len(scoreAry)//2) :
	print(scoreAry[i][0], ':' , scoreAry[len(scoreAry)-1-i][0])

Self11-01.py

최댓값 찾기 함수를 직접 구현합니다

def findMaxIdx(ary) :

    maxIdx = 0
    for i in range(1, len(ary)) :
        if (ary[maxIdx] < ary[i] ) :
            maxIdx = i
    return maxIdx

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

Self11-01.py

Implements a find-maximum function yourself

def findMaxIdx(ary) :

    maxIdx = 0
    for i in range(1, len(ary)) :
        if (ary[maxIdx] < ary[i] ) :
            maxIdx = i
    return maxIdx

testAry = [55, 88, 33, 77]
minPos = findMaxIdx(testAry)
print('Maximum -->', testAry[minPos])

Self11-02.py

삽입 정렬을 직접 구현합니다

import  random
## 함수 선언부
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 = []
after = []

## 메인 코드부

before = [random.randint(0,200) for _ in range(10)]
print('정렬 전 -->', before)
for i in range(len(before)) :
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('정렬 후 -->', after)

Self11-02.py

Implements insertion sort yourself

import  random
## Function Declarations
def findInsertIdx(ary, data) :

    findIdx = -1  # Initial value set to invalid position
    for i in range(0, len(ary)) :
        if (ary[i] < data ) :
            findIdx = i
            break
    if findIdx == -1 : # No larger value found == last position
        return len(ary)
    else :
        return findIdx

## Global Variables
before = []
after = []

## Main Code
before = [random.randint(0,200) for _ in range(10)]
print('Before sorting -->', before)
for i in range(len(before)) :
    data = before[i]
    insPos = findInsertIdx(after, data)
    after.insert(insPos, data)
print('After sorting -->', after)

🧪 Ch11. 정렬 (기본) — 실습 코드 / Lab Code: Sorting (Basic)

📘 교재 예제 (Code)

📘 Textbook Examples (Code)

📗 응용 예제 (Ex)

📗 Applied Examples (Ex)

📙 자가 실습 (Self)

📙 Self Practice (Self)