알골 1번(Python) - 선택 정렬 & 이진 검색

1부터 1024까지의 정수 중 랜덤하게 10개를 뽑아 배열을 생성, 선택정렬으로 정렬한다.

이후 사용자에게서 정수를 입력받고 배열에서 그 정수와 일치하는 값의 index를 반환하는 알고리즘을 작성하였다.

일치하는 값이 없다면 찾는 수가 없습니다. 라는 문구가 뜨도록 작성하였다.

---

 

전체 코드

import random

def sorting(randomList):
    for i in range(len(randomList)-1):
        for j in range(i,len(randomList)):
            if randomList[i]>randomList[j]:
                randomList[i],randomList[j] = randomList[j],randomList[i]

def search(num, list, start, end):
    dev = (start+end)//2
    if start <= end:
        if list[dev]==num:
            return dev
        elif list[dev] > num:
            return search(num, list, start, dev-1)
        elif list[dev] < num:
            return search(num, list, dev+1, end)
    else:
        return '찾는 수가 없습니다.'
    
while(1):
    randomList = random.sample(range(1,1025),10)
    print(randomList)
    sorting(randomList)
    print(randomList)
    user_input=int(input("number : "))
    print(search(user_input, randomList, 0, 9))

 

선택 정렬

def sorting(randomList):
    for i in range(len(randomList)-1):
        for j in range(i,len(randomList)):
            if randomList[i]>randomList[j]:
                randomList[i],randomList[j] = randomList[j],randomList[i]

1부터 1024까지 랜덤한 정수 10개를 저장한 배열을 인자로 받는 함수 작성.

선택 정렬을 통해 오름차순으로 정렬.

 

선택 정렬 알고리즘 예시

이중 for문의 두번째 for 문을 통해 j가 i부터 배열의 끝까지 항목들을 검사한다.

배열의 i번째 값보다 큰 값이 있으면 위 그림처럼 두 개의 자리를 바꾼 후 다시 i번째 값을 배열의 나머지값들과 비교한다.

 

이진 검색

def search(num, list, start, end):
    dev = (start+end)//2
    if start <= end:
        if list[dev]==num:
            return dev
        elif list[dev] > num:
            return search(num, list, start, dev-1)
        elif list[dev] < num:
            return search(num, list, dev+1, end)
    else:
        return '찾는 수가 없습니다.'

사용자가 입력한 정수(num), 검색한 값을 찾으려는 배열(list), 배열의 시작 지점(start), 배열의 끝 지점(end) 값을 인자로 가지는 이진 검색 함수 작성.

배열에 없는 값을 입력했을 때 '찾는 수가 없습니다' 라는 문구 출력.

 

이진 검색 알고리즘 예시

간단한 이진 검색 알고리즘

실행 결과

실행 결과

 

 

피드백은 언제나 환영입니다. 감사합니다!