C++ 삽입정렬, 선택정렬, 버블 정렬

삽입 정렬

10

9 8 7 6 5 4 3 2 1 0

8 9 7 6 5 4 3 2 1 0 

7 8 9 6 5 4 3 2 1 0 

6 7 8 9 5 4 3 2 1 0 

5 6 7 8 9 4 3 2 1 0 

4 5 6 7 8 9 3 2 1 0 

3 4 5 6 7 8 9 2 1 0 

2 3 4 5 6 7 8 9 1 0 

1 2 3 4 5 6 7 8 9 0 

0 1 2 3 4 5 6 7 8 9 

해당 index 보다 뒤에 있는 모든 값을 살펴 보고 만약에 값이 작다면 바꿔준다. 

4 8 11 14 23 5 3 2 4 9 이렇게 바꿔준다.

#include <iostream>

using namespace std;

int main() {

int num;

cin >>num;

int array[num];

int temp;

for(int i=0;i<num;i++)

cin >> array[i];

for(int i=1;i<num;i++)

{

for(int j=i;j>=1;j--)

{

if(array[j]<array[j-1])

{

temp = array[j];

array[j]= array[j-1];

array[j-1]=temp;

}

else break;

}

}

for(int i=0;i<num;i++)

cout<< array[i]<<" ";

return 0;

}

---------------------------------------------------------------------------------]------------

선택 정렬

배열이

10 2 2 3 5 8

i

라고 가정하면

1. 10에서 8까지 모든 수를 비교한다.

2. 가장 작은 수와 10을 바꿔준다.

3. i 를 한칸 이동한다. 다시 1,2번 반복

2 10 2 3 5 8

    i

2  2 10 3 5 8

        i    

#include <iostream>

#include <vector>

using namespace std;

int total[101][101];

int plane[100];

int main() {

int num;

cin>>num;

int array[num];

for(int i=0;i<num;i++)

cin >> array[i];

int temp;

for(int i=0;i<num;i++)

{

int inx = i;

for(int j=i;j<num;j++)

{

if(array[inx]>array[j])

inx=j;

}

temp= array[inx];

array[inx]=array[i];

array[i]=temp;

}

for(int i=0;i<num;i++){

cout<< array[i]<<" ";

}

return 0;

}

10

4 3 2 3 7 7 1 2 9 1

>입력한 값

1 3 2 3 7 7 4 2 9 1 

1 1 2 3 7 7 4 2 9 3 

1 1 2 3 7 7 4 2 9 3 

1 1 2 2 7 7 4 3 9 3 

1 1 2 2 3 7 4 7 9 3 

1 1 2 2 3 3 4 7 9 7 

1 1 2 2 3 3 4 7 9 7 

1 1 2 2 3 3 4 7 9 7 

1 1 2 2 3 3 4 7 7 9 

1 1 2 2 3 3 4 7 7 9 

>변화 하는 모습

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

버블 정렬

ex)

4 7 8 9 1 2 3 10 

num =9;

i : 0

j : 0 1 2 3 4 5 6 7 8 

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

i : 1 

j : 0 1 2 3 4 5 6 7

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

i : 2

j : 0 1 2 3 4 5 6 

버블 정렬은 값 중에서 가장 큰 값을 끝으로 모는 방식이다. 

( 버블이 물방울이기 때문에 물위로 떠오른다를 생각하면 쉽다. ) 

j 와 i 를 설정하기 어렵지만 조금만 생각하면 쉽다. 

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int num;

cin >>num;

int array[100];

for(int i =0;i<num;i++)

cin >> array[i];

for(int i=0;i<num;i++)

{

for(int j=0;i<num-i-1;j++)

{

if(array[j]>array[j+1])

{

int temp;

temp = array[j+1];

array[j+1]= array[j];

array[j] = temp;

}

}

for(int j=0;j<num;j++)

cout<< array[j];

}

return 0;

}

---------

응용

100개가 넘는 숫자중에서 3번째로 큰 수를 구하시오!!

라고 한다면 

버블 정렬 사용하는게 효율적이다. 이유는 버블을 3번만 쏘아 올리면 되기 때문이다.