[CodeKata] 17. bubbleSort

그냥·2022년 7월 5일
0

CodeKata

목록 보기
18/18

문제

버블정렬(Bubble Sort)

버블 정렬은 인접한 데이터를 교환해서 정렬하는 알고리즘입니다. 알고리즘의 정렬되는 모습이 마치 거품처럼 보인다고 해서 붙여진 이름입니다.

아래와 같은 정렬되지 않은 수가 있을 때, index 0 <-> 1 부터 교환하기 시작합니다. 인접한 두 수를 비교하여 더 큰 것을 우측으로 이동시킵니다. 6 5 3 2 8 -> 5 6 3 2 8

그 다음은 index 1 <-> 2 5 6 3 2 8 -> 5 3 6 2 8

그 다음은 index 2 <-> 3 5 3 6 2 8 -> 5 3 2 6 8

그 다음은 index 3 <-> 4 5 3 2 6 8 -> 5 3 2 6 8 이렇게 제일 마지막 두 수 까지 비교하면, 제일 큰 수가 제일 마지막 index에 위치하는 것을 알 수 있습니다.

다시 처음부터 시작합니다. 5 3 2 6 8 -> 3 5 2 6 8

3 5 2 6 8 -> 3 2 5 6 8

3 2 5 6 8 -> 3 2 5 6 8 이번 교환에는 index 2까지 비교하고 멈추면 됩니다. 마지막 index는 이미 제일 큰 수가 정렬된 상태이기 때문입니다. 이런식으로 계속 비교하고 교체하면 됩니다.!

Problem
nums라는 배열을 주면, 버블정렬 알고리즘으로 배열을 정렬해주세요.


풀이


1. 문제의 조건 정리
1) 정수로 이루어진 배열을 인자로 받는다.
2) 정수로 이루어진 배열을 반환한다.
3) 버블정렬을 사용해서 배열을 오름차순으로 정렬한다.

2. 조건에 대한 코드 구현 방법 생각
1) 이중 for문을 사용한다.
2) 첫 번째 for문에서는 len(nums)-1 부터 0까지 내려간다.
3) 두 번째 for문에서는 첫 번째 for문에서 받은 인자의 범위만큼 for문을 돌린다.
4) 만약 nums[j] > nums[j+1]이면 swap을 한다.

3. 구현 코드
def bubbleSort(arr):
	for i in range(len(arr)-1, 0, -1):
    	for j in range(i):
        	if nums[j] > nums[j+1]:
            	nums[j], nums[j+1] = nums[j+1], nums[j]
                
    return arr

4. 코드 리뷰
1) for문을 돌리면서 특정 인덱스에서 for문을 돌린 후 그 이후의 값에서 이제 swap할 여지가 없다면 바로 for문을 중단할 수 있는 방법이 있으면 좋을 것 같다.

5. 최고의 코드
def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        swapped = False
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

0개의 댓글