[알고리즘] 01. 버블정렬

안녕하세요? 주니하랑 입니다.

오늘은 자료구조와 알고리즘의 알고리즘에서 Bubble Sort에 대해 공부 해 보도록 하는 것이에요.

소스 코드에 대해서 확인 하고 싶으신 분들께서는 주니하랑의 Git hub에 관심을 주세요!

 

 

---

 

 

📌 Sorting (정렬)이란?

---

정렬은 어떤 Data가 주어졌을 때, 이를 정해진 순서대로 나열하는 것이에요.

정렬은 Program 작성 시 빈번하게 필요하답니다! 때문에 다양한 알고리즘이 존재하고, 이를 공부해야 하는 것이에요.

다양한 정렬 알고리즘을 이해하게 된다면 동일한 문제에 대해 다양한 알고리즘을 생각해 볼 수 있게 되고, 각 알고리즘 간의 성능 비교를 통해, 성능 분석에 대해서는 이해할 수 있답니다!

 

 

 

📌 Bubble Sort (버블 정렬)란?

---

두 인접한 Data를 서로 비교해서 앞에 있는 Data가 뒤에 있는 Data보다 크다면 자리를 바꾸는 정렬 알고리즘 인 것이에요.

 

참고 사이트 : https://visualgo.net/ko/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

 

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

 

 

 

 

 

 

 

주니하랑 필기본

 

 

    📍 Data가 네 개 일때

data_list = [1, 9, 3, 2]

• 1차 Round
  • 1과 9 비교, 1이 작기 때문에 자리 이동 필요없음
    현재 값 [1, 9, 3, 2]
  • 9와 3을 비교, 9가 3보다 크기 때문에 자리 이동
    현재 값 [1, 3, 9, 2]
  • 9와 2를 비교, 9가 2보다 크기 때문에 자리 이동
    현재 값 [1, 3, 2, 9]
• 2차 Round
  • 1과 3을 비교, 1이 작기 때문에 자리 이동 필요없음
    현재 값 [1, 3, 2, 9]
  • 3과 2를 비교, 3이 크기 때문에 자리 이동
    현재 값 [1, 2, 3, 9]
  • 3과 9를 비,교 3이 작기 때문에 자리 이동 필요없음
    현재 값 [1, 2, 3, 9]
• 3차 Round
  • 1과 2를 비교, 1이 작기 때문에 자리 이동 필요없음
    현재 값 [1, 2, 3, 9]
  • 2와 3을 비교, 2가 작기 때문에 자리 이동 필요없음
    현재 값 [1, 2, 3, 9]
    3과 9를 비교, 3이 작기 때문에 자리 이동 필요없음
    현재 값 [1, 2, 3, 9]

 

 

 

 

 

 

📌 알고리즘 구현

---

    📍 반복되는 규칙 찾기

           🛎 n개의 List가 있을 때, 최대 n-1번의 Logic이 적용
           🛎Round를 1번씩 거칠 때 마다 가장 큰 숫자가 뒤에서부터 1개씩 자리를 잡는다.
           🛎위의 이유로 Round가 경우에 따라 일찍 끝날 수도 있다. 따라서 Round를 적용할 때, 한 번도 앞과 뒤 사이 데이터
                 교환이 없었다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요 없다.

 

 

    📍 Python 형식으로 적어보기

for num in range(len(data_list)):	# 반복
	swap = False	# Data 교환이 이뤄졌는지 확인하는 변수 선언 및 초기화
    
    for num1 in range(len(data_list) - num - 1): # 반복문 안에서 n -1 번 반복해야 하기 때문에
    	# 반복문 안에서 앞에 Index의 값이 뒤에 Index 값보다 크다면?
        if data_list[num1] > data_list[num1 + 1]: 
        	# 서로 Data 위치를 바꿔준다.
        	data_list[num1], data_list[num1 + 1] = data_list[num1 + 1], data_list[num1]
            
            # 한번이라도 Data 교환이 이뤄졌다면 if문에 들어왔을 것이고, swap변수를 True로 바꾼다.
            swap = True		
            
    if swap == False:		# 한 Round를 도는데, Data의 교환이 한번도 이뤄지지 않았다면
    	break				# 이미 Data가 정렬되었다고 판단할 수 있기 때문에 반복문을 종료한다.

 

 

---

 

 

주니하랑의 글이 마음에 드셨나요? 구독과 공감! 그리고, 댓글은 주니하랑에게 많은 힘이 됩니다