CS50 2019 (9)bubble sort, selection sort

===

www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)

1.컴퓨팅사고

2.C언어

3.배열

4.알고리즘

5.메모리

6.자료구조

 

---

선택! 해서 앞에거랑 바꾸는 것

 

조건이 낀 버블인가봐

 

---

4)버블 정렬

사물함에서 가운데 찍고 반씩 제꼈던 방법은 사실

조교가 모든 숫자가 정렬할 때까지 기다려야 하는 price pay가 있었음

 

그렇다면 정렬하는 데 얼마나 많은 시간이 필요할지 알면

꼭 정렬한 후 숫자를 찾아야할지 // 아니면 정렬을 하지 않고 바로 탐색하는게 좋을지 선택할 수 있다.

 

▽정렬도 비용이므로 (정렬+이진탐색 vs 선택)  하는게 더 정확한 비교

 

===

일단 정렬되지 않은 숫자들의 입력이 주어지고, 목표는 숫자를 정렬하여 반환하는 것, 어떻게 구현할까?

6 3 8 5 2 7 4 1 을 오름차순으로!

친구들 멋있네 얘네들이 번호를 하나씩 들고 사람 위치를 바꿔서 정렬할거야

 

지시자가 사람들에게 

첫번째 두번째 사람 크기 비교해서 왼쪽이 크면 바꾸고 아니면 안바꾸고

똑같이 23 비교해서 바꿀까 말까 하고... 끝까지 해서 반복

-> 여기까지 한번, 문제가 해결되진 않았지만 조금이라도 정답에 가까워졌다 왜냐? 맨 오른쪽 숫자는 올바른 위치를 찾아왔다.

▽한번 더 반복하면? n-1번째 숫자가 올바른 위치를 찾았다

▽n-1번 반복하면 정렬된다

▽일단 컴퓨터는 한칸씩 밖에 확인을 못한다는걸 알려줬었지 여기서 : 이런 설명이 진짜 최고다

▽근데 1234657 이라고 돼 있으면 첫번째 시도에서 1234567이라고 돼 있어도 컴퓨터는 그게 맞는 정렬인걸 확인할 길이 없다

▽처음부터 정렬이 다 돼 있는 입력값이라면 아무것도 안해도 되겠지만, 아무리 가장 많이 걸리는 입력값에도 n-1번 처음부터 끝까지 다 확인 한번씩 다 하면 정렬이 됐다고 확신을 가질 수가 있다.(밑에 오메가 설명과는 다른게 그냥 이건 직관적으로 정말 정렬이 되는지 안되는지를 이해하려고 하는 설명)

 

여기서 정렬한 방법은 사실 버블 정렬이라는 알고리즘이다.

거품이 떠오르듯 8이 왼쪽에서 오른쪽으로 움직이고...  ▽한턴에 젤 큰거 한개가 오른쪽 끝으로 제자릴 찾네

 

의사코드로 적으면

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

Repeat n-1 times

왜 n-1이냐면 n명이 있고 서로를 비교한다면 최대 n-1번을 비교 할 수 있다(▽한개씩 제자릴 찾는데 마지막은 안해도 되니까?)

 

처음 1, 2 바꿔주세요 그다음 2, 3 비교했고 그다음 3, 4 번쨰 사람들 비교했고..  한턴 끝

이걸 n-1번 반복함

 

  For i from 0 to n-2  --왜 n-2냐 0부터 시작했으니까, 그리고 밑에 i랑 i+1를 바꾸라고 한다, i가 0이면 0과 1번째를..

  (사람을 배열로 보는중)i기 0부터 시작할 때

    i번째 사람과 i+1번째 사람의 순서가 잘못됐다면

      Swap them

      자리를 바꿔주세요 

 

의사코드 : 정렬하라는 지시사항을 이처럼 숫자와 단어 몇 개로 간결하게 표현을 할 수 있습니다.

 

===

버블 정렬 실행 시간의 Big-O표기는 어떻게 될까?

바깥 반복문은 n-1반복하고,

안쪽 반복문 또한 n-1번 반복함(0부터 n-2까지니까요)

이 수식을 곱해서 정리해보면

중요한건 n이 커질수록 지수가 가장 큰 n^2의 영향력이 가장 크므로 컴퓨터 과학자는 버블정렬이 

아까 봤던 상한선 목록에선

즉 버블 정렬을 사용하면, 선형 탐색이나 이진 탐색보다 더 시간이 많이 든다는 겁니다.

 

그럼 Eirc과 Nizari의 알고리즘 중 Nizari의 알고리즘이 더 좋았는데(빨랐어서) 사실은 정렬을 필요로 했다는 가정이 있었다.

 

그렇기 때문에 이진 탐색이 선형 탐색보다 좋다고 하는 건 맞지 않다!

많은 시간을 들여서 항목을 미리 정렬한 후에야 이진 탐색을 시작할 수 있었으니까

딱히 이득이 없거나 오히려 더 느릴수도

 

그럼 어따써?

배열에 대해 여러 번 탐색을 해야 하는 경우(이번엔 얘 찾고 다음에 와서 쟤 찾고)라면 한 번 정렬해두는 게 좋을 것(▽사전 단어가 무작위라면 선형탐색 해야 되잖아). 그럼 빠른 검색으로 장기적인 이득을 볼 수 있다

▽여러번 탐색 해야 되는것에 정렬을 해둔 뒤 이진 탐색하는게 더 이득

 

===

버블 정렬의 Omega는?

의사코드를 보면 좋은 입력값이 주어져도 크게 달라지지 않는다 ▽입력값에 따르는군 당연한거

정렬 알고리즘에서 가장 좋은 입력값은?이미 정렬된거겠지 할일이 없는데

하지만 그 운이 좋은 상황에서도 버블 정렬은 무식하게 동작함.

(의사코드를 보면)이미 정렬돼 있어도 종료하라는 말이 없음

그저 맹목적으로 n-1번, 내부에서도 n-2번 반복함

버블 정렬의 실행 시간의 하한선은 이미 정렬된 배열이 들어와도 여전이 n^2다! 여전히 같은 횟수를 반복해야 하기 때문임

버블 정렬의 하한선 즉 Omega는 n^2가 된다!

 

===

네이버 : 어떤 배열이 주어졌을 때, 그 배열이 미리 정렬되어 있다면 훨씬 빠른 속도로 검색이 가능합니다. 정렬하기 위한 방법은 여러가지가 있고, 각각 실행 시간도 다릅니다. 이번 강의에서는 그 중 하나인 버블 정렬을 배워 보겠습니다.

 

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다.

정렬 알고리즘 중 하나는 버블 정렬입니다.

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.

이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.

아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있습니다.

이 숫자들을 오름차순으로 정렬하기 위해 바로 옆의 있는 숫자들과 비교하는 방법을 사용해 보겠습니다.

 

6 3 8 5 2 7 4 1

 

먼저 가장 앞의 6과 3을 비교해서 순서를 바꿉니다.

 

교환 전: 6 3 8 5 2 7 4 1

교환 후: 3 6 8 5 2 7 4 1

 

다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둡니다.

바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꿉니다.

 

교환 전: 3 6 8 5 2 7 4 1

교환 후: 3 6 5 8 2 7 4 1

 

이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 됩니다.

 

3 6 5 2 7 4 1 8

 

하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복합니다.

 

3 6 5 2 7 4 1 8

3 6 5 2 7 4 1 8 (교환)

3 5 6 2 7 4 1 8 (교환)

3 5 2 6 7 4 1 8 

3 5 2 6 7 4 1 8 (교환)

3 5 2 6 4 7 1 8 (교환)

3 5 2 6 4 1 7 8

 

조금 더 잘 정렬이 되었습니다. 이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것입니다.

 

1 2 4 3 5 6 7 8

 

이러한 정렬 방식을 ‘버블 정렬’이라고 합니다.

마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문입니다.

아래와 같이 의사 코드로 나타낼 수 있습니다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로  (n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n​2​​−3n+2  번의 비교 및 교환이 필요합니다.

여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 Ω(n^2)이 됩니다.

 

=====================

5)선택 정렬

버블정렬과 근본적으로 다른 접근법인 선택 정렬

버블정렬의 장점 : 알기 쉽다. 왼쪽 오른쪽 보고 작은 문제를 풀어나가는

 

하지만 근본적으로, 정렬이라는 문제를 생각해보면

작은 값은 왼쪽으로, 큰 값은 오른쪽에 두는 방법은 어떨까?

 

63852741

가장 작은 수가 뭘까? 숫자들은 배열에 들어있다

(서랍에 들어있다고 생각해야 한다 컴퓨터는 열어서 확인을 해봐야 아는거니까)사람처럼 직관적인 방법을 사용할 수 없다

 

그럼 어떻게 가장 작은 수를 아냐면

6 하나 꺼내서 보면 지금까지 본 숫자중에 가장 작아, 변수에 담기

3 하나 꺼내서 보면 이땐 얘가 제일 작아, 6들어있던 변수에 담아

8..

5..

2나오면 걔 담고

7..

4..

1나오면 걜 담고

 

가장 작은게 나왔다 어떻게 맨 앞으로 둬? 두가지 방법이 있음

- 맨 앞 비우게 전부 한칸씩 옮기거나(시간이 꽤 오래걸려)

- 해당 위치 숫자를 쫓아내고 거기다 두는 것, 쫓아낸건 아무데나(숫자들 사이에) 두면 됨 어차피 순서는 임의였으니

(▽아예 쫓아내면 안되고 앞으로 계속 비교를 해야하는 숫자이니 내가 확인하는 범위 내에 둬야해) 

 

그럼 1이 제자리에 놓여있다.

배열이 조금 정렬됐고, 이제 n-1개를 확인하면 됨

 

같은 방식으로 반복

사람이라면 제일 작은게 1이었으니 중간에 2가 나오면 아 이거네 하고 바로 갖다 놓고 싶겠지만 그 뒤에 2보다 더 작은 게 있나 봐야함

2를 끝까지 확인해보니 이것보다 더 작은게 없으니 두번째 자리에 있는애를 쫓아내고 얘를 둬

...

반복

 

===

쌍을 이뤄 앞뒤 순서를 교환하는 방식과 근본적으로 다름

매번 목표를 세워 가장 작은 값을 찾고 다음 작은 값을 찾는 방법임!

 

*습관적으로 길들이세요 앞으로 어떤 상황에서든 n개의 항목이 있다면

첫 번째 항목은 0번째라고 하고,

마지막 항목을 n-1번째라고 한다.(특히 이거)

컴퓨터 과학자는 0부터 n-1을 1부터 n을 세기 위해 사용한다.

 

===

의사코드로는 이렇다

For i from 0 to n–1  -- i를 써서 n번 반복하려면 0부터 n-1까지다

  Find smallest item between i'th item and last item  *i'th는 i번째

  :  between은 얘부터 얘 중에서, i을 0으로 초기화 한다면, 8개 중에서 가장 작은 항목을 찾으란 말

   i가 1이 되면 7개 중에서구나. 이후로 n-2, n-3...

    Swap smallest item with i'th item

    : 그리고 그 항목을 i번째 항목과 교환합니다!

∴ 제일 작은 항목을 찾을 때마다 집어 들어서 위치를 바꿉니다, 그리고 반복

 

===

그럼 선택 정렬이 더 나을까?

낫다의 의미로 두 가지 도구가 있다

Big-O 와 Omega

 

8개 있으면 총 7번의 과정이 필요함, 어떤게 제일 작은지 확인 하는 하나 하나가 한번

첫번째 과정에선 거의 8, n번의 확인이 필요함. 모든 항목을 다 살펴보니까   --거의 라는말 왜 했지?

그 다음 7, n-1개가 남는데 n-1번의 확인이 필요

두번 하면 n-2,

n-3, n-4...

마지막엔 1개만 남음

n + n-1 + n-2 + .... + 1 인 것

미국인들은 부록에서나 볼 수 있는 수학공식, 하나 더 작은 수를 계속 더하면 이런 관계식이 나옴

곱셈을 풀면 Big-O표기법에서 중요한건, (n이 커질수록 n^2가 가장 빠르게 증가해서 중요하기 때문에) 신경써야 할 부분은 n^2

 

따라서 선택정렬 또한 O(n^2) 알고리즘

근본적으로 다른 알고리즘이지만 수학적으로는, 그리고 실제로는 같은 성능을 갖는다

 

===

선택정렬의 Omega는? :

이미 정렬된 배열을 받아도? 맹목적으로 똑같은 횟수를 반복하나?

응

12345678이어도

컴퓨터는 첫번째 서랍을 열어 1을 발견했을 때 다른 수에 대한 정보가 없다(눈은 다른것도 슉 하고 다봄)

프로그램은 배열 속 다른 값을 전부 보기 전까지 알 수 없다

선택정렬을 사용해도 앞에 놓인 수만 알 수 있기 때문에 같은 코드를 계속 반복

횟수도 똑같고 최선의 경우에도 시간을 낭비함

니까요

 

===

네이버 :

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다.

정렬을 위한 알고리즘 중 선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.

▽교환! 비교! 이게 각각 하나씩의 횟수인가보네?

다음과 같은 정렬되지 않은 숫자들을 오름차순 정렬해보도록 하겠습니다.

6 3 8 5 2 7 4 1

먼저 아래 숫자들 중에서 가장 작은 값을 찾습니다.

6 3 8 5 2 7 4 1

가장 작은 값인 1은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값인 6과 교환합니다.

1 3 8 5 2 7 4 6

그리고 정렬되어 있는 1은 제외하고, 두 번째 숫자부터 시작해서 또 가장 작은 값을 찾습니다.

1 3 8 5 2 7 4 6

가장 작은 값인 2는 정렬되지 않는 숫자들 중에서 가장 앞에 있어야 하므로 3과 교환합니다.

1 2 8 5 3 7 4 6

이 과정을 더 이상 교환이 일어나지 않을때까지 반복하면, 아래와 같이 오름차순 정렬이 완료됩니다.

1 2 3 4 5 6 7 8

 

이러한 정렬 방법을 ‘선택 정렬’ 이라고 합니다. 의사 코드로 아래와 같이 표현할 수 있습니다.

For i from 0 to n–1

  Find smallest item between i'th item and last item 

    Swap smallest item with i'th item

여기서도 두 번의 루프를 돌아야 합니다.

바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야 합니다.

따라서 소요 시간의 상한은 O(n^2)이 됩니다. 하한도 마찬가지로 Ω(n^2) 입니다. 버블 정렬과 동일합니다. 

-- 루프 하나가 n인가? 그럴걸 교환 한번 하는게 1번이니까

 

=====================

6)정렬 알고리즘의 실행시간 (줄이기)

문제에 대한 나쁜 해답을 2개나 배웠다

더 잘할 수 없을까?

 

버블정렬 알고리즘은 n-1번(끝까지) 반복하라고 했지만 여기에 알고리즘을 멈추거나, 줄이는 조건문이 있으면 좋을 것

'12 23 34 ... 끝까지 해도 교환이 없을 때' 가 정렬이 된 것이므로 이때 까지만 반복하도록

Repeat n–1 times   ->  Repeat until no swaps 로만 바꾸면 됨

For i from 0 to n–2

If i'th and i+1'th elements out of order

Swap them

최선의 경우에는 n-1번만 하면 됨 1~8이면 12 23 34 45 56 67 78 7번

하한선이 Ω(n)이 됨

조금만 머리를 써서 알고리즘의 실행 시간을 줄였음

 

네이버 : 

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n)
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n)
• Ω(n)
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보겠습니다.

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까요?

바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 하면?

최종적으로 버블 정렬의 하한은 Ω(n)이 됩니다

 

===

--- 어떤 사이트 가서 버블, 선택 정렬 실제로 되는 걸 눈으로 보여주는 수업 내용중 교환 교환 교환 ---

보면 직관적으로 딱 와닿는게

- 지금까지 중에 제일 큰건 계속 오른쪽으로 가고,

- 걔보다 작은건 왼쪽으로 한칸씩 가.

- 시행마다 제일 큰게 오른쪽에 쌓여

 

===

선택 정렬 보는데 가장 작은 값을 왼쪽부터 채워 넣는다

가장 작은 값을 색칠해서 표시를 한다

 

버블정렬 : 큰 값이 오른쪽으로 떠오르고

선택정렬 : 가장 작은 값을 제자리에 차례차례 둔다