[Python] 파이썬 기초 20/20, 선택정렬 퀵정렬 이진검색 성능비교

<내용정리>

- 관련 파일

선택정렬01.py

0.00MB

선택정렬02.py

0.00MB

선택정렬03.py

0.00MB

이진검색.py

0.00MB

정렬_성능비교.py

0.00MB

- 본문

1) 선택정렬 1

### 배열에서 최솟값의 위치를 찾는 함수
def findMinIdx(ary):
    minIdx = 0  # 배열의 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])

 

 

2) 선택정렬 2

### 선택 정렬의 구현
def findMinIdx(ary):
    minIdx = 0  # 배열의 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)

 

3) 선택정렬 3

### 선택 정렬의 구현
import random
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
        ary[i], ary[minIdx] = ary[minIdx], ary[i]
    return ary

dataAry = [random.randint(1, 100) for _ in range(8)]
print('정렬 전 -->', dataAry)
dataAry = selectionSort(dataAry)
print('정렬 후 -->', dataAry)

 

 

4) 이진검색

### 정렬된 데이터의 이진 검색
def binSearch(ary, fData):
    pos = -1
    start = 0
    end = len(ary) - 1  # 맨끝

    while start <= end:
        mid = (start + end) // 2
        if fData == ary[mid]:
            return mid
        elif fData > ary[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return pos

dataAry = [50, 60, 105, 150, 160, 162, 168, 177, 188]
print('# 배열-->', dataAry)
findData = int(input('# 찾을 값을 입력하세요--> '))
position = binSearch(dataAry, findData)
if position == -1:
    print(f'{findData}이/가 없네요')
else:
    print(f'{findData}이/가 {position} 위치에 있음')

 

 

5) 성능비교

### 선택 정렬과 퀵 정렬의 성능 비교
import random
import time

## 퀵 정렬
def quickSort(ary):
    n = len(ary)
    if n <= 1:
        return ary
    pivot = ary[n//2]  # 기준값을 중간값으로 지정
    # 기준보다 작은 데이터를 저장할 왼쪽 배열,
    # 기준보다 큰 데이터를 저장할 오른쪽 배열 준비
    leftAry, rightAry = [], []
    for num in ary:
        if num < pivot:
            leftAry.append(num)
        elif num > pivot:
            rightAry.append(num)
    # 재귀 호출해서 정렬한 후 반환
    return quickSort(leftAry) + [pivot] + quickSort(rightAry)

## 선택 정렬
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
        ary[i], ary[minIdx] = ary[minIdx], ary[i]
    return ary

## 메인 코드 부분
# 임의로 생성할 데이터 개수를 배열에 미리 저장
countAry = [1000, 10000, 12000, 15000]
for count in countAry:
    tempAry = [random.randint(10000, 99999) for _ in range(count)]
    selectAry = tempAry[:]  # 선택 정렬 배열에 복사
    quickAry = tempAry[:]  # 퀵 정렬 배열에 복사

    print(f'## 데이터 수 : {count}개')
    start = time.time()  # 선택 정렬 시작 시간 설정
    selectionSort(selectAry)  # 선택 정렬 수행
    end = time.time()  # 선택 정렬 끝 시간 설정
    print(f'선택 정렬 --> {end-start:8.3f}초')

    start = time.time()
    quickSort(quickAry)
    end = time.time()
    print(f'퀵 정렬 --> {end-start:10.3f}초')