[파이썬 자료구조와 알고리즘] Chapter 11. 정렬 기본

학습 목표

• 정렬 개념 파악
• 정렬을 위한 코드 형식 이해
• 기본적인 정렬 방식 학습
• 정렬을 활용한 응용 프로그래밍 작성

 

Section00. 생활 속 자료구조와 알고리즘

대학교: 학생들 원하는 자리에 맘대로 앉음

교수 출석부에는 학번 순서나 이름 순서로 명단 작성됨

요리사도 칼 여러 개 사용하는데 가능하면 칼 크기대로 가지런히 놓고 사용하는 것을 좋아함

-정렬: 순서대로 데이터가 나열되어 있는 것

 

 

Section01. 정렬의 기본

1. 정렬의 개념

-정렬(Sort): 자료들을 일정한 순서대로 나열하는 것

-순서대로 나열할 때: 작은 것부터 나열하는 방법/큰 것부터 나열하는 방법

-오름차순 정렬(Ascending Sort): 작은 것부터 큰 순으로 나열된 방법

-내림차순 정렬(Descending Sort): 큰 것부터 먼저 나열하는 방법

 

2. 정렬 알고리즘의 종류

🌴선택 정렬(Selection Sort)

🌴삽입 정렬(Insertion Sort)

🌴버블 정렬(Bubble Sort)

🌴퀵 정렬(Quick Sort)

 

 

Section02. 기본 정렬 알고리즘의 원리와 구현

1. 선택 정렬

🤎선택 정렬의 개념

-선택 정렬(Selection Sort): 여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬하는 방식

이 방식으로 계속 차례대로 정렬하면 오름차순으로 정렬할 수 있다.

 

🤎최솟값을 찾는 방법

가장 작읍 값을 참는 함수가 필요

①배열의 첫 번째 값을 가장 작은 값으로 지정

②가장 작은 값으로 지정한 값을 다음 차례의 값과 비교하여 가장 작은 값을 변경하거나 그대로 두는 방법

③마지막 값까지 비교를 마친 후 현재 가장 작은 값으로 지정된 값을 가장 작은 값으로 결정

->한 마디로 비교하여 바꾼다

def findMinUdx(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])

 

🤎선택 정렬 구현

미리 배열 크기를 지정한 후 사용(예시)

ary=[None for _ in range(3)]
ary[0]=100
ary[1]=200
ary[2]=300

빈 배열을 준비한 후 append() 함수로 배열에 ㄱ밧을 추가하기만 하면 배열 크기가 자동으로 늘어남

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]):
        	minIdx=1
    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)

 

🤎두 변수 값 교환

원칙적으로 한 번에 두 변수의 값을 교환할 수 없으므로 임시공간 사용하기

파이썬에서는 임시 공간 없이 A변수와 B변수를 한 행으로 변경하는 문법 제공

#1)
temp=A
A=B
B=temp

#2)
A, B= B, A

🤎개선된 선택 정렬 구현

앞에서는 선택 정렬 전 배열, 정렬 후 배열 2개를 사용

하지만 배열 하나로 데이터를 정렬하는 방식이 더 효율적

맨 앞의 값을 가장 작은 값으로 지정한 후 나머지 값과 비교해서 제일 작은 값 찾기

그 다음에 작은 값 나오면 비교하여 변경

마무리에서는 가장 작은 값을 앞으로 위치시킴

그 다음 사이클 2에서 맨 앞을 가장 작은 값으로 우선 지정하고 나머지 값들과 비교하여 제일 작은 값을 찾음

모든 사이클이 완료되면 배열에는 정렬된 결과가 남음

#클래스와 함수 선언 부분
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
        tno=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)

🤎선택 정렬 성능

O(n^2)

입력 개수가 커질수록 기하급수적으로 비교 횟수가 늘어나기에 성능이 나쁜 알고리즘

 

 

2. 삽입 정렬

🤎삽입 정렬의 개념

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

 

🤎삽입 위치를 찾는 방법

현재 값을 배열 중에 삽입할 위치를 찾는 함수가 필요

삽입 정렬의 전제 조건: 삽입할 위치를 찾는 기존 배열을 이미 정렬되어 있다는 점

 

빈 배열일 때는 첫 번째 자리에 삽입

배열에 삽입할 값보다 큰 값이 있을 때는 처음부터 비교해 가면서 자신보다 큰 값을 만나면 그 값 바로 앞에 삽입

배열에 삽입할 값보다 큰 값으 없을 때는 맨 뒤에 삽입

빈 배열일 때와 배열에 삽입할 값보다 큰 값이 없을 때는 동일하게 작동

 

배열에서 자신이 삽입될 위치를 찾는 함수

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)

🤎삽입 정렬 구현

insert(삽입할 위치, 값) 함수를 사용하면 간단

testAry=[]
testAry.insert(0, 55)
testAry

여러 개가 있는 상태에서 1번째 위치에 55 삽입

testAry=[33, 77, 88]
testAry.insert(1, 55)
testAry

배열의 맨 뒤에 값 삽입

4번째 위치에 100 삽입

testAry=[33, 55, 77, 88]
testAry.insert(4, 100)
testAry

삽입 정렬의 구현

#클래스와 함수 선언
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]
arter=[]

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

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

🤎삽입 정렬의 효율적인 구현

배열을 2개 사용하는 것보다 배열 하나에서 데이터를 정렬하는 방식이 더 효율적

간단하게 4개의 데이터를 정렬할 때 배열크기-1회의 큰 반복을 해야 함

마찬가지로 이 큰 반복을 사이클이라고 하며, 예에서는 데이터가 4개이므로 총 3회의 사이클 필요

처음에는 앞에 2개, 다음에는 3개, 그 다음에는 4개 처리

#클래스와 함수 선언 부분
def insertionSort(ary):
	n=len(ary)
    for end in range(1, n): #1부터 시작하므로 배열 크기-1 횟수만큼 반복
    	for cur in range(end, 0, -1): #첨자인 end 변수는 각 사이클의 끝 위치를 지정,
        	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)

🤎삽입 정렬 성능

O(n^2)

입력 개수 커질수록 기하급수적으로 늘어남

성능 안 좋아

 

 

 

Section03. 기본 정렬 알고리즘의 응용

1. 1차원 배열의 중앙 값 계산

🤎평균과 중앙값

데이터 값 중에서 비정상적인 수치가 섞여 있을 때는 평균값을 대푯값으로 사용하기 어려움

 

🤎중앙값 계산

-중앙값: 데이터를 일렬로 정렬해서 나열한 후 나열된 숫자의 가운데에 위치하는 값을 대푯값으로 하는 방법

선택 정렬 사용한 중앙 값 계산

#클래스와 함수 선언 부분
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(mondeyAry)
print('용돈 저열 후-->', moneyAry)
print('용돈 중앙 값-->', moneyAry[len(moneyAry)//2])

 

2. 파일 이름의 정렬 출력

🤎지정된 폴더에서 하위 폴더를 포함한 파일 목록 추출

c:\Windows\System32 폴더 파일 배열에 저장하는 기능을 하는 코드

import os

fnameAry\[]
folderName='C:/Windows/System32'
for dirName, subDirList, fnames in os.walk(floderName):
	for fname in fnames:
    	fnameAry.append(fname)
        
print(len(fnameAry))

🤎파일 목록 정렬

파일='파일명.확장명'

파일명 및 확장명으로 분리해서 정렬

파일 목록 배열을 파일명으로 내림차순 정렬한 결과와 확장명으로 내림차순 정렬한 결과를 출력하는 코드(삽입 정렬)

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)

 

 

<연습문제>

1. 정답)4

2. 정답) 2 재귀 정렬

3. 정답) 4

속도 느림

4. minIdx=0

0, len(ary)-1

minIdx=i

 

5. 정답)1

6. 정답)3 O(n^2)

7. 4

8.

findIdx=-1

return len(ary)

return findIdx