2.1 순차 정렬(Sequential Sort)
이번에는 반복적인 방법으로 해결하는 순차 정렬(Sequential Sort) 알고리즘을 살펴볼게요.
정렬 알고리즘은 배열의 자료를 원하는 순으로 배치하는 알고리즘을 말해요. 정렬 알고리즘은 입력 인자로 정렬할 자료들이 있는 배열의 시작 주소와 원소 개수, 비교 알고리즘이 필요합니다. 그리고 수행 후에는 배열 내의 자료들은 원하는 순서로 배치한 상태여야 합니다.
순차 정렬은 맨 앞에서부터 제일 작은 원소를 배치하게 만들어 나가는 알고리즘이예요. 이를 위해 배치할 자리에 있는 원소를 뒤쪽에 있는 원소들과 비교하면서 작은 것을 발견하면 배치할 위치의 원소와 교환해요.
순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
반복(j:=i+1->n)
조건(compare(base[i], base[j]) > 0)
교환(base[i],base[j])
예:
2 9 4 1 5 6 8 3 7 (정렬 전, n:9)
2 9 4 1 5 6 8 3 7 (i:0, j:1)
2 9 4 1 5 6 8 3 7 (i:0, j:2)
2 9 4 1 5 6 8 3 7 (i:0, j:3)
1 9 4 2 5 6 8 3 7 (i:0, j:3) - 교환
1 9 4 2 5 6 8 3 7 (i:0, j:4)
1 9 4 2 5 6 8 3 7 (i:0, j:5)
1 9 4 2 5 6 8 3 7 (i:0, j:6)
1 9 4 2 5 6 8 3 7 (i:0, j:7)
1 9 4 2 5 6 8 3 7 (i:0, j:8) - 1회전 완료
1 9 4 2 5 6 8 3 7 (i:1, j:2)
1 4 9 2 5 6 8 3 7 (i:1, j:2) - 교환
1 4 9 2 5 6 8 3 7 (i:1, j:3)
1 2 9 4 5 6 8 3 7 (i:1, j:3) - 교환
1 2 9 4 5 6 8 3 7 (i:1, j:4)
1 2 9 4 5 6 8 3 7 (i:1, j:5)
1 2 9 4 5 6 8 3 7 (i:1, j:6)
1 2 9 4 5 6 8 3 7 (i:1, j:7)
1 2 9 4 5 6 8 3 7 (i:1, j:8) - 2회전 완료
1 2 9 4 5 6 8 3 7 (i:2, j:3)
1 2 4 9 5 6 8 3 7 (i:2, j:3) - 교환
1 2 4 9 5 6 8 3 7 (i:2, j:4)
1 2 4 9 5 6 8 3 7 (i:2, j:5)
1 2 4 9 5 6 8 3 7 (i:2, j:6)
1 2 4 9 6 6 8 3 7 (i:2, j:7)
1 2 3 9 6 6 8 4 7 (i:2, j:7) - 교환
1 2 3 9 5 6 8 3 7 (i:2, j:8) - 3회전 완료
...생략...
2.1.1 순차 정렬 알고리즘 분석
이번에는 순차 정렬 알고리즘의 타당성 및 수행 속도를 계산해 보기로 해요.
순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
반복(j:=i+1->n)
조건(compare(base[i], base[j]) > 0)
교환(base[i],base[j])
순차 정렬의 내부 반복문은 j값이 i+1에서 n까지 변하죠. 그리고 i번째와 j번째 요소와 비교하여 i번째 원소가 크면 교환하기 때문에 i번째에서 j번째 원소 중에 제일 작은 값은 언제나 i번째에 존재합니다. 따라서 내부 반복문을 수행하면 i에서 마지막 원소 중에 제일 작은 값이 i번째에 배치함을 알 수 있어요.
외부 반복문은 i값이 0에서 n까지 변하죠. 그리고 내부 반복문을 통해 i번째에서 마지막 원소 중에 제일 작은 원소를 i번째에 배치하므로 i번 앞에 있는 원소는 정렬 상태를 유지합니다. 따라서 루프 변성인 i가 n까지 변하는 성질과 루프 불변성인 i번째 앞에 있는 원소는 정렬 상태를 유지한다는 특징을 통해 위 알고리즘을 수행하면 정렬할 수 있음을 알 수 있습니다.
이번에는 수행 속도를 접근식 표기 방식으로 계산해 보아요.
내부 반복문을 수행하는 시간을 S(i, n)이라고 하면 n-i 번 비교하고 교환 횟수는 최악일 때 n-i번이예요. 따라서 S(i, n) <= n-i(비교횟수) + n-2(최악의 교환 횟수) = 2(n-i)
외부 반복문은 i가 0~n-1까지 변하면서 내부 반복문을 수행합니다. 따라서 외부 반복문을 수행하는데 걸리는 시간을 T(n)이라고 하면 S(0,n)+S(1,n)+...+S(n-1,n)입니다.
T(n) = S(0,n) + S(1,n) + ... + S(n-1,n) = 2n + 2(n-1) + ... + 2
따라서 다음과 같이 표현할 수 있어요.
T(n) = 2n + 2(n-1) + ... + 2
T(n) = 2 + ... + 2(n-1) +2n
따라서 2T(n) = 2(n+1) + 2(n+1) + 2(n+1)
T(n) = (n+1) + (n+1) +... +(n+1)
n+1을 n번 더한 값이므로 T(n) = n(n+1) = n^2 + n 으로 표현할 수 있죠.
점근식 표기에서는 가장 높은 차수의 항만 사용하고 상수를 버리므로 O(n^2)라고 말할 수 있어요.
2.1.2 공통으로 사용할 코드 구현
앞으로 이 책에서는 다양한 정렬 알고리즘을 구현할 거예요. 먼저 공통으로 사용할 코드를 구현합시다.
정렬에 사용할 데이터는 문자열과 번호를 멤버로 갖는 형식으로 정의할게요. 그리고 테스트에서는 이름 순으로 정렬도 해 보고 번호로 정렬도 해 보기로 해요.
테스트에 사용할 데이터 형식을 Member 클래스라 정할게요.
class Member
{
멤버 필드로 이름과 번호를 선언하세요.
string name;
int num;
public:
생성자에서 이름과 번호를 입력 인자로 받아 멤버 필드를 설정하세요.
Member(string name,int num)
{
this->name = name;
this->num = num;
}
이름과 번호 멤버 필드에 접근할 수 있게 접근자 메서드를 제공하세요.
string GetName()const
{
return name;
}
int GetNum()const
{
return num;
}
개체 정보를 출력하는 메서드도 제공합시다.
void View()const
{
cout<<setw(10)<<setfill('0')<<num<<","<<name<<endl;
}
};
번호로 비교하는 함수와 이름으로 비교하는 함수도 필요하겠죠.
int CompareByNum(Member *m1, Member *m2)
{
int n1 = m1->GetNum();
int n2 = m2->GetNum();
return n1 - n2;
}
int CompareByName(Member *m1, Member *m2)
{
string n1 = m1->GetName();
string n2 = m2->GetName();
return n1.compare(n2);
}
랜덤한 회원 개체를 원하는 개수만큼 생성해서 배열에 설정하는 함수도 제공합시다. 회원 개체를 동적으로 생성하면 Member * 형식으로 사용하므로 배열을 입력 인자로 받으려면 Member ** 형식으로 받으면 되겠죠.
void MakeRandomMembers(Member **pbase, size_t n)
{
for(size_t i=0; i<n; i++)
{
번호는 랜덤 함수를 이용할게요. 랜덤 함수가 반환하는 값은 0~32767이어서 두 번 호출한 곱으로 합시다.
int num = rand()*rand();
char buf[256];
이름도 접미사에 랜덤한 수를 넣게 만듭시다.
sprintf_s(buf,sizeof(buf),"이름%010d",rand()*rand());
pbase[i] = new Member(buf,num);
}
}
동적으로 만든 회원 개체들을 소멸하는 함수도 제공해야겠죠.
void RemoveMembers(Member **pbase, size_t n)
{
for(size_t i=0; i<n; i++)
{
delete pbase[i];
}
}
회원 개체를 보관한 배열의 원소를 출력하는 함수도 작성합시다.
void ViewMembers(Member **pbase, size_t n)
{
for(size_t i=0;i<n; i++)
{
pbase[i]->View();
}
}
다음은 공통으로 사용할 common.h 파일의 내용이예요.
//common.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <iomanip>
#include <iostream>
#include <string>
#include <time.h>
using namespace std;
class Member
{
string name;
int num;
public:
Member(string name,int num)
{
this->name = name;
this->num = num;
}
string GetName()const
{
return name;
}
int GetNum()const
{
return num;
}
void View()const
{
cout<<setw(10)<<setfill('0')<<num<<","<<name<<endl;
}
};
int CompareByNum(Member *m1, Member *m2)
{
int n1 = m1->GetNum();
int n2 = m2->GetNum();
return n1 - n2;
}
int CompareByName(Member *m1, Member *m2)
{
string n1 = m1->GetName();
string n2 = m2->GetName();
return n1.compare(n2);
}
void MakeRandomMembers(Member **pbase, size_t n)
{
for(size_t i=0; i<n; i++)
{
int num = rand()*rand();
char buf[256];
sprintf_s(buf,sizeof(buf),"이름%010d",rand()*rand());
pbase[i] = new Member(buf,num);
}
}
void RemoveMembers(Member **pbase, size_t n)
{
for(size_t i=0; i<n; i++)
{
delete pbase[i];
}
}
void ViewMembers(Member **pbase, size_t n)
{
for(size_t i=0;i<n; i++)
{
pbase[i]->View();
}
}
2.1.3 순차 정렬 알고리즘 구현
이번에는 순차 정렬 알고리즘을 구현해 보기로 해요.
순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
반복(i:=0->n)
반복(j:=i+1->n)
조건(compare(base[i], base[j]) > 0)
교환(base[i],base[j])
자료 형식에 관계없이 정렬할 수 있게 템플릿 함수로 작성합시다.
template <typename data, typename compare>
//순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void sequential_sort(data *base, size_t n, compare com)
{
순차 정렬에서는 인덱스 0에서 n까지 최소값을 배치하는 것을 반복하죠.
for(size_t i = 0; i<n; i++) //반복(i:=0->n)
{
내부 반복문에서는 i 뒤에 원소들을 비교하면서 교환하는 것을 반복합니다.
for(size_t j=i+1; j<n; j++)//반복(j:=i+1->n)
{
만약 i번째 원소가 j번째 원소보다 더 크면 두 원소를 교환하죠.
if(com(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
{
swap(base[i],base[j]); //교환(base[i],base[j])
}
}
}
}
이제 테스트 코드를 작성합시다. 정렬할 원소 개수를 매크로 상수로 정의하세요.
#define MAX_DATA 1000
int main()
{
Member *base[MAX_DATA];
먼저 정렬 알고리즘을 간단히 테스트 하기 위해 회원 개체를 10개만 생성하세요.
MakeRandomMembers(base,10);
정렬 전의 회원 개체 배열을 출력하세요.
cout<<"정렬 전"<<endl;
ViewMembers(base,10);
번호 순으로 순차 정렬합시다. 그리고 정렬후에 회원 개체 배열을 출력하세요.
sequential_sort(base,10,CompareByNum);
cout<<"번호로 정렬 후"<<endl;
ViewMembers(base,10);
이름 순으로 순차 정렬합시다. 그리고 정렬 후에 회원 개체 배열을 출력하세요.
sequential_sort(base,10,CompareByName);
cout<<"이름으로 정렬 후"<<endl;
ViewMembers(base,10);
정렬에 사용한 회원 개체 배열을 해제화를 해야겠죠.
RemoveMembers(base,10);
이번에는 알고리즘 성능을 테스트 해 보아요. 알고리즘을 수행 전과 수행 후에 clock을 측정하여 차이를 계산하면 수행 속도를 평가할 수 있어요.
clock_t st,et;
먼저 MAX_DATA 개수의 회원 개체를 생성하여 이름 순으로 정렬한 후에 속도를 출력하세요.
MakeRandomMembers(base,MAX_DATA);
cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
st = clock();
sequential_sort(base,MAX_DATA,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA);
그리고 MAX_DATA/10 개수의 회원 개체를 생성하여 이름 순으로 정렬한 후에 속도를 출력하세요.
MakeRandomMembers(base,MAX_DATA/10);
cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
st = clock();
MakeRandomMembers(base,MAX_DATA/10);
sequential_sort(base,MAX_DATA/10,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA/10);
return 0;
}
다음은 테스트에 사용한 전체 코드입니다.
//Program.cpp
#include "common.h"
template <typename data, typename compare>
//순차 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
void sequential_sort(data *base, size_t n, compare com)
{
for(size_t i = 0; i<n; i++) //반복(i:=0->n)
{
for(size_t j=i+1; j<n; j++)//반복(j:=i+1->n)
{
if(com(base[i],base[j])>0)//조건(compare(base[i], base[j]) > 0)
{
swap(base[i],base[j]); //교환(base[i],base[j])
}
}
}
}
#define MAX_DATA 1000
int main()
{
Member *base[MAX_DATA];
MakeRandomMembers(base,10);
cout<<"정렬 전"<<endl;
ViewMembers(base,10);
sequential_sort(base,10,CompareByNum);
cout<<"번호로 정렬 후"<<endl;
ViewMembers(base,10);
sequential_sort(base,10,CompareByName);
cout<<"이름으로 정렬 후"<<endl;
ViewMembers(base,10);
RemoveMembers(base,10);
clock_t st,et;
MakeRandomMembers(base,MAX_DATA);
cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;
st = clock();
sequential_sort(base,MAX_DATA,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA);
MakeRandomMembers(base,MAX_DATA/10);
cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;
st = clock();
MakeRandomMembers(base,MAX_DATA/10);
sequential_sort(base,MAX_DATA/10,CompareByName);
et=clock();
cout<<"수행 속도:"<<et-st<<endl;
RemoveMembers(base,MAX_DATA/10);
return 0;
}
이를 수행하였을 때 나온 결과예요. 물론 수행하는 컴퓨터에 따라 결과는 조금씩 다를 수 있어요.
▷수행 결과
정렬 전
0000757147,이름0167851000
0301413356,이름0336971124
0659598368,이름0160567225
0391749387,이름0004890851
0035766290,이름0026239572
0473038164,이름0000597006
0003615544,이름0326051436
0392289610,이름0118341522
0170427798,이름0037215528
0675016433,이름0168544290
번호로 정렬 후
0000757147,이름0167851000
0003615544,이름0326051436
0035766290,이름0026239572
0170427798,이름0037215528
0301413356,이름0336971124
0391749387,이름0004890851
0392289610,이름0118341522
0473038164,이름0000597006
0659598368,이름0160567225
0675016433,이름0168544290
이름으로 정렬 후
0473038164,이름0000597006
0391749387,이름0004890851
0035766290,이름0026239572
0170427798,이름0037215528
0392289610,이름0118341522
0659598368,이름0160567225
0000757147,이름0167851000
0675016433,이름0168544290
0003615544,이름0326051436
0301413356,이름0336971124
수행 성능 테스트1 자료 개수:1000
수행 속도:4985
수행 성능 테스트2 자료 개수:100
수행 속도:50
수행 결과를 보면 번호 순과 이름 순으로 정렬하는 것을 알 수 있습니다.
그리고 수행 성능을 테스트 한 것을 보면 자료의 개수를 MAX_DATA로 할 때가 MAX_DATA/10으로 할 때보다 100배 가까이 느린 것을 알 수 있습니다.
순차 정렬 알고리즘을 분석하였을 때 계산한 O(n^2)와 결과가 비슷한 것을 알 수 있습니다.
알고리즘 성능을 분석할 때 수학적으로 계산해서 증명할 수 있으면 좋겠죠. 만약 그렇지 못한다면 지금처럼 실제 수행 시간을 측정하여 비교해 보세요.
'언어 자료구조 알고리즘 > [C++]디딤돌 자료구조와 알고리즘' 카테고리의 다른 글
| 3.1 배열과 vector [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
|---|---|
| 3. 선형 자료구조 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 2.4 삽입 정렬(Insertion Sort) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 2.3 선택 정렬(Selection Sort) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 2.2 거품 정렬 (Bubble Sort) [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 2. 반복 알고리즘 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 1.3 점근식 표기 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 1.2 알고리즘 소개 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 1.1 자료구조와 STL [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |
| 1. 소개 [디딤돌 자료구조와 알고리즘 with C++] (0) | 2016.04.04 |