버블 정렬 (bubble sort)
이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.
잔재미코딩 소식 공유
좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을
오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다
● 잔재미코딩 유투브 오픈
[구독해보기]
3. 대표적인 정렬1: 버블 정렬 (bubble sort)¶
0. 알고리즘 연습 방법¶
- 알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함
- 모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작
이번 챕터부터 알고리즘 시작입니다.!
1. 연습장과 펜을 준비하자.
2. 알고리즘 문제를 읽고 분석한 후에,
3. 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.
4. 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
5. 코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,
6. 각 문장을 코드 레벨로 적는다.
7. 데이터 구조 또는 사용할 변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서, 임의 데이터로 코드가 정상 동작하는지를 연습장과 펜으로 검증한다.
1. 정렬 (sorting) 이란?¶
- 정렬 (sorting): 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것
- 정렬은 프로그램 작성시 빈번하게 필요로 함
- 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수
다양한 정렬 알고리즘 이해를 통해, 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해, 알고리즘 성능 분석에 대해서도 이해할 수 있음
2. 버블 정렬 (bubble sort) 란?¶
- 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘
직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting¶
3. 어떻게 코드로 만들까?¶
알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다.
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
프로그래밍 연습
데이터가 두개 일때 동작하는 버블 정렬 알고리즘을 함수로 만들어보세요
데이터가 두개 일때 동작하는 버블 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 연습
데이터가 세개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
데이터가 세개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
프로그래밍 연습
데이터가 네개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
데이터가 네개 일때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요
- 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.)
- 예: 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]
- 1차 로직 적용
- 예: data_list = [1, 9, 3, 2]
4. 알고리즘 구현¶
- 특이점 찾아보기
- n개의 리스트가 있는 경우 최대 n-1번의 로직을 적용한다.
- 로직을 1번 적용할 때마다 가장 큰 숫자가 뒤에서부터 1개씩 결정된다.
- 로직이 경우에 따라 일찍 끝날 수도 있다. 따라서 로직을 적용할 때 한 번도 데이터가 교환된 적이 없다면 이미 정렬된 상태이므로 더 이상 로직을 반복 적용할 필요가 없다.
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
가장 빠르게 풀스택 개발자가 될 수 있도록, 최적화된 로드맵을 제공합니다
- for num in range(len(data_list)) 반복
- swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
- 반복문 안에서, for index in range(len(data_list) - num - 1) n - 1번 반복해야 하므로
- 반복문안의 반복문 안에서, if data_list[index] > data_list[index + 1] 이면
data_list[index], data_list[index + 1] = data_list[index + 1], data_list[index]swap += 1- 반복문 안에서, if swap == 0 이면, break 끝
In [2]:
import random
data_list = random.sample(range(100), 50)
In [3]:
def bubble_sort(data):
for index in range(len(data_list)):
swap = 0
for index2 in range(len(data_list) - 1 - index):
if data_list[index2] > data_list[index2 + 1]:
data_list[index2], data_list[index2 + 1] = data_list[index2 + 1], data_list[index2]
swap += 1
if swap == 0:
break
return data_list
In [ ]:
bubble_sort(data_list)
5. 알고리즘 분석¶
- 반복문이 두 개 O($n^2$)
- 최악의 경우, $\frac { n * (n - 1)}{ 2 }$
- 완전 정렬이 되어 있는 상태라면 최선은 O(n)
본 자료와 같이 IT 기술을 잘 정리하여, 온라인 강의로 제공하고 있습니다
체계적으로 전문가 레벨까지 익힐 수 있도록 온라인 강의 로드맵을 제공합니다
프로그래밍 연습
지금 설명한 삽입 정렬을 알고리즘 연습 방법에 따라서, 다시 스스로 작성해보세요
지금 설명한 삽입 정렬을 알고리즘 연습 방법에 따라서, 다시 스스로 작성해보세요