[Algorithm][Python] 버블정렬 bubble sort

버블정렬

1. 정렬 이란?

• 정렬(sorting) : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
• 정렬은 프로그램 작성시 자주 필요
• 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수

  다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해, 각 알고리즘 간 성능비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있음

2. 버블 정렬 이란? (buble sort)

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘.

• 직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

출처: https://en.wikipedia.org/wiki/Bubble_sort

3. 어떻게 코드로 만들까?

알고리즘 연습 방법에 기반해서 단계별로~

1. 간단한 예시를 통해 규칙을 찾자.
   • 예를 들어서 길이가 2, 3, 4 인 실 예시를 만들고 해보자.
2. 인접한 데이터를 비교해서 정렬하는 경우, 시행횟수가 어떻게 되는지 알아보았다.
   • arr.length 가 n 일 경우, 0번째 요소부터 마지막 요소까지 비교는 n-1 번 실행
3. 첫번째 순회에서 n-1 번 실행하면, 가장큰 숫자가 맨 오른쪽으로 가게됨
4. 두번째는 그다음 큰 수가 맨오른쪽으로 가게됨.
5. 맨오른쪽 숫자는 가장큰수로 고정이므로, n-1-i 가 되겠다.
6. 한번 순회하는데 스왑이 없다면, 이미 정렬이 된 것이므로 더이상의 비교는 무의미.

def bubbleSort(data):
	for index in range(len(data) - 1):
		swap = False
		for index2 in range(len(data) - 1 - index):
			if(data[index2] > data[index2 + 1]):
				data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
				swap = True
		if swap == False:
		  break;

	return data

4. 알고리즘 분석

• 반복문이 두개이므로 O(n²) 이다.

5. 번외 (윗첨자와 아래첨자)

윗첨자는 ^string^ 아랫첨자는 ~string~ 혹은 html 태그로도 가능하다 . <sup>. <sub> 로도 가능!