정렬 (1)

 

* 정렬

 

1) Bubble sort

배열에서 이웃하는 두 원소씩 차례대로 정렬하는 작업을 반복함으로써 배열 전체를 정렬하는 알고리즘이다.

두 원소를 정렬하는 과정을 (배열 원소수 - 1)만큼 반복한다.

단계마다 맨 뒤부터 정렬이 된다.

 

 

5

4

3

2

1

 

- 1 -                           

4

3

2

1

5

- 2 -

3

2

1

4

5

- 3 -

2

1

3

4

5

- 4-

1

2

3

4

5

 

 

2) Selection sort

항목을 모든 항목과 비교하여 가장 작은 항목부터 선택하여 정렬하는 알고리즘이다.

단계마다 맨 앞부터 정렬이 된다.

 

5

4

2

1

3

 

- 1 -

1

4

2

5

3

- 2 -

1

2

4

5

3

- 3 -

1

2

3

5

4

- 4 -

1

2

3

4

5

 

 

 

3) Insertion sort

배열 원소들을 좌우로 정렬된 부분과 정렬되지 않은 부분으로 나눈 후 정렬되지 않는 부분의 원소를

정렬된 부분의 자리에 한개씩 삽입하여 모든 원소를 정렬하는 알고리즘이다.

 

5

4

2

1

3

       TarGet

4

- 1 -   

4

5

2

1

3

TarGet

2

- 2 -   

2

4

5

1

3

TarGet

1

- 3 -   

1

2

4

5

3

TarGet

3

- 4 -   

1

2

3

4

5

 

 

 

# 대소문자 구분 안함

#include <iostream>
using namespace std;

void copy_array(char *a, char *b);
void Bubble_sort(char *a);
void select_sort(char *a);
void insert_sort(char *a);

int main()
{
 char copy[10];
 char a[10];

 cout<<"Input 10 alphabet : ";
 for(int i=0; i<10; i++)
  cin>>a[i];
 
 cout<<"-------------- bubble_sort ---------------\n"; 
 copy_array(a,copy);           
 Bubble_sort(copy);           
 cout<<"-------------- select_sort ---------------\n";
 copy_array(a,copy);          
 select_sort(copy);          
 cout<<"-------------- insert_sort ---------------\n";
 copy_array(a,copy);          
 insert_sort(copy);          

 return 0;
}

void copy_array(char *a, char*b)
{
 for(int i=0; i<10; i++)
  b[i] = a[i];   // 단순 복사
}

void Bubble_sort(char* a)
{
 int i,j,flag;
 int count=0;
 int temp,temp1,temp2;

 for(i = 0; i < 9; i++)
 {
  flag = 0;
  for(j = 0; j < 8; j++)
  {       
   temp1 = a[j];
   temp2 = a[j+1];
   if(temp1 < 97)
    temp1 = temp1 + 32;
   if(temp2 < 97)
    temp2 = temp2 + 32;
                      
   if(temp1>temp2)           
   {   
    temp = a[j];
    a[j] = a[j+1];
    a[j+1] = temp;
    flag = 1;
   }

  }
  if(flag == 1)
  {
   count++;
   cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<" "<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9];
   cout<<"  count : "<<count<<endl;

  }
 }
}

void select_sort(char* a)
{
 int i,j,index,flag;
 int count=0;
 int temp,temp1,temp2;

 for(i = 0; i < 9; i++)
 {
  flag = 0;
  index = i;                 
  for(j = i+1; j < 10; j++)
  {  
   
   temp1 = a[index];
   temp2 = a[j];
   if(temp1 < 97)
    temp1 = temp1 + 32;
   if(temp2 < 97)
    temp2 = temp2 + 32;
      
   if(temp1>temp2)
   {
    index = j;
    flag = 1;
   }
  }
  temp = a[i];    
  a[i] = a[index];
  a[index] = temp;
  
  if(flag == 1)
  {
   count++;
   cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<" "<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9];
   cout<<" count : "<<count<<endl;
  }
 }
}

void insert_sort(char *a)
{
 int i,j,target,flag;
 int count=0;
 int temp1,temp2;

 for(i=1; i<10; i++)
 {
  flag = 0;
  target = a[i];  

  for(j=i-1; j >= 0; j--)  
  {
   temp1 = target;
   temp2 = a[j];
   if(temp1 < 97)
    temp1 = temp1 + 32;
   if(temp2 < 97)
    temp2 = temp2 + 32;

   if(temp1<temp2)
   {
    a[j+1] = a[j];     
    flag = 1;
   }   
   else
    break;
  }
  a[j+1] = target;
  if(flag == 1)
  {
   count++;
   cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<" "<<a[4]<<" "<<a[5]<<" "<<a[6]<<" "<<a[7]<<" "<<a[8]<<" "<<a[9];
   cout<<" count : "<<count<<endl;
  }
 }
}