버블정렬.

버블 정렬은 인접한 데이터를 교환해서 정렬하는 알고리즘입니다.

인접한 두 수를 비교하여 더 큰 것을 우측으로 계속 이동시키면 됩니다.
idex 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는 이미 제일 큰 수가 정렬된 상태이기 때문입니다.

이런식으로 계속 비교하고 교체하면 됩니다.

참고자료 :
https://visualgo.net/en/sorting

굳이 그런데.. 저는 버블정렬이라는것을 사용해야하는건가 ?? 라는 물음을 스스로에게 던졌다.

데이터수가 적을때는 상관이 없을것 같지만
데이터가 많을때 , 하나하나 다 비교하는건데 그게 과연 효율적인 것일까 ??
라는 생각을 했다 .물론.. 아직 공부가 부족한 나이기에 정답도 모르겠고 잘 모르지만
스스로 다른 더 효율적으로 sort 할수는 없을까?? 라는 생각을 했다 .

import random

data_list =random.sample(range(100) ,50 )

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


print(bubbleSort(data_list))

알고리즘 분석

• 반복문이 두개 O(n^2)
  최악의 경우 , n*(n-1)/2
• 완전 정렬이 되어 있는 상태라면 최선은 O(n)