알고리즘 감 살리기 - 기초 알고리즘

알고리즘 감 살리기 - 기초 알고리즘

군대에서 꾸준히 하루에 3문제씩 알고리즘을 풀었었는데, 복학하고 점점 안푸니까 실력이 너무 녹슬었다.
다시금 알고리즘 감을 살리기 위해 기초부터 시작하려 한다.

버블 정렬

버블 정렬은 요소 목록을 반복적으로 살펴보고 인접한 요소를 비교하고 순서가 잘못된 경우 교체하는 간단한 정렬 알고리즘입니다.
거품이 액체 표면으로 올라가는 것과 유사하게 작은 요소가 목록의 맨 위로 "거품"되기 때문에 이름이 붙여졌습니다.

아래는 제가 작성한 코드입니다.

def bubbleSort(numbers):  
	for i in range(len(numbers) - 1):  
		for j in range(i + 1, len(numbers)):  
			if numbers[i] > numbers[j]:  
				temp = numbers[i]  
				numbers[i] = numbers[j]  
				numbers[j] = temp  
return numbers

다음 인덱스의 값이 현재 인덱스보다 크다면 값을 교환합니다

아래는 GPT가 최적화한 코드입니다.

def bubbleSortGpt(numbers):
    n = len(numbers)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if numbers[j] > numbers[j + 1]:
                numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
                swapped = True
        if not swapped:
            break
    return numbers

swap 플래그를 둬서 이미 정렬되었다면 배열 선회를 멈춥니다.

눈여겨 보아야 할 것은 큰 수가 제일 위로 올라가도록 정렬 되어 있으므로,
내부 루프의 범위를 줄여 불필요한 반복을 피하였습니다

선택 정렬

선택 정렬은 입력을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누어 작동하는 간단한 정렬 알고리즘입니다.
알고리즘은 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 정렬되지 않은 부분의 첫 번째 요소와 교체하여 정렬된 부분을 한 요소씩 확장합니다

def selection_sort(n):
    length = len(n)
    for i in range(length - 1):
        min_index = i
        for j in range(i + 1, length):
            if n[j] < n[min_index]:
                min_index = j
        if min_index != i:
            n[i], n[min_index] = n[min_index], n[i]
    return n

print(selection_sort([1, 4, 2, 3, 5]))

삽입 정렬

삽입 정렬은 한 번에 한 요소씩 최종 정렬된 배열을 만드는 간단한 비교 기반 정렬 알고리즘입니다.
입력 목록을 정렬된 하위 배열과 정렬되지 않은 하위 배열로 나누어 작동합니다. 처음에 정렬된 하위 배열에는 첫 번째 요소만 포함되고 정렬되지 않은 하위 배열에는 나머지 요소가 포함됩니다.

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j + 1] = data[j]
            j -= 1
        data[j + 1] = key
    return data

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>