CS50 4. 알고리즘(2) - 선형 검색, 버블 정렬, 선택 정렬

선형 검색

• 찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘이 있는데 그 중 하나가 선형 검색
• 선형검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다
• 이렇게 하여 선형 검색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 한다

 

효율성 그리고 비효율성

• 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법
• 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행
• 여기서 최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우
• 반대로 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우
• 평균적으로 선형 검색이 최악의 상황에서 종료되는 것에 가깝다고 가정할 수 있다.
• 선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용
• 이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적

 

위와 같은 이유로 왜 검색 이전에 정렬해줘야 하는지 알 수 있다. 정렬은 시간이 오래 걸리고 공간을 더 차지한다.

하지만 이 추가적인 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시간을 단축할 수 있다.

 

주어진 배열에서 특정 값을 찾기 위해서 선형 검색을 사용한다면, 아래와 같은 코드를 작성할 수 있다.

배열의 크기만큼 for 루프를 돌면서 배열의 인덱스를 차례대로 방문하며 찾는 값이 있는지를 검사하기

 

 

문자열로 이루어진 배열도 비슷한 방식으로 검색할 수 있다.

만약 전화번호부에서 특정 이름을 찾아 해당하는 전화번호를 출력하는 프로그램을 작성하려면?

가장 간단한 예는 아래와 같은 프로그램이 될 것

 

names 배열과 numbers 배열을 따로 정의하고 names 배열에서 검색을 해서 해당하는 인덱스의 numbers 배열 값을 출력하는 것

하지만 이 경우에는 names 배열과 numbers 배열이 서로 같은 인덱스를 가져야 한다는 한계가 있다.

더 좋은 방법은 아래 코드와 같이 새로운 자료형으로 구조체를 정의해서 이름과 번호를 묶어주는 것

 

 

person 이라는 이름의 구조체를 자료형으로 정의하고 person 자료형의 배열을 선언하면 그 안에 포함된 속성값은 ‘.’으로 연결해서 접근할 수 있다. ( person a; 라는 변수가 있다면, a.name 또는 a.number 이 각각 이름과 전화번호를 저장하는 변수가 되는 것)

이렇게 함으로써 더욱 확장성 있는 전화번호부 검색 프로그램을 만들 수 있다.

 

버블 정렬

• 정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적
• 정렬 알고리즘 중 하나는 버블 정렬
• 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법
• 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중
• 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다

----------------------------------------------------------------------------------------------------------------------
아래와 같은 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

 

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

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

----------------------------------------------------------------------------------------------------------------------

 

버블 정렬의 의사코드

중첩 루프를 돌아야 하고, 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)

 

선택 정렬

• 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬
• 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가

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

 

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

----------------------------------------------------------------------------------------------------------------------

 

선택정렬의 의사코드

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

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

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