[패스트캠퍼스 :: 코딩테스트 인강] 5주차 ② 정렬 / 버블 정렬

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

기본 정렬 알고리즘 - 01. 정렬 알고리즘 개요

기본 정렬 알고리즘 - 02. 버블 정렬 - 1

기본 정렬 알고리즘 - 02. 버블 정렬 - 2

 

---

2021.03.21

 

 

자료구조와 알고리즘의 차이는 무엇일까?

공부하면서 알다가도 모를 부분이었다.

 

하지만 공부를 하다 보니, 그 궁금증이 해소가 되는 것 같았다.

 

자료구조는 데이터가 저장되는 형태 즉 데이터 표현 및 저장 방식을 의미한다면,

알고리즘은 그렇게 데이터가 저장되어 있는 형태인 자료구조에서 데이터를 명령 처리 및 제어하기 위한 방법을 구현하는 것이다.

 

앞서 4주 동안은 데이터 저장 방식인 자료구조에 대하여 학습하였다면,

앞으로 대략 4주 정도는 자료구조에서 원하는 데이터를 검색, 정렬 등의 명령/제어를 하기 위한 알고리즘 방법을 학습할 것이고,

이러한 알고리즘까지 학습하게 되면,

코딩 테스트 뿐만 아니라 다양한 문제 해결을 위하여 구현할 수 있을 것 같다.

 

 

---

버블 정렬 (bubble sort) 란?

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

 

 

 

버블 정렬 방식

 

데이터가 네 개 일 때 (데이터 개수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)

• 예: data_list = [1, 9, 3, 2]
  • 1차 로직 적용
    • 1 와 9 비교, 자리바꿈 없음 [1, 9, 3, 2]
    • 9와 3 비교, 자리바꿈 [1, 3, 9, 2]
    • 9와 2 비교, 자리바꿈 [1, 3, 2, 9]
  • 2차 로직 적용
    • 1과 3 비교, 자리바꿈 없음 [1, 3, 2, 9]
    • 3과 2 비교, 자리바꿈 [1, 2, 3, 9]
    • 3과 9 비교, 자리바꿈 없음 [1, 2, 3, 9]
  • 3차 로직 적용
    • 1 과 2 비교, 자리바꿈 없음 [1, 2, 3, 9]
    • 2와 3 비교, 자리바꿈 없음 [1, 2, 3, 9]
    • 3과 9 비교, 자리바꿈 없음 [1, 2, 3, 9]

 

알고리즘 구현을 위한 NoteTaking

 

1. for num in range(len(data_list)) 반복
2. swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
3. 반복문 안에서, for index in range(len(data_list) - num - 1) n - 1번 반복해야 하므로
4. 반복문 안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
5. data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]
6. swap += 1
7. 반복문 안에서, if swap == 0 이면, break 끝

 

코드 구현

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - index - 1):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2] # swap 하는 형태 구현 방법
                swap = True
        
        if swap == False:
            break
    return data

 

 

 

---

 

정렬의 종류가 워낙 많아서 앞으로 헷갈리지 않게 잘 정리해두어야 할 것 같고,

이는 정보처리기사 필기/실기 시험에서도 잘 나오는 알고리즘 방법이기 때문에 중요한 것 같다.

 

하지만 앞으로 코딩 테스트 문제 유형에서는 어떻게 적용을 시켜야 할지 아직 감이 잘 안 잡힌다.

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스