정렬1

매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.

버블정렬 / 선택정렬 / 삽입정렬

모두 시간복잡도는 O(n^2)이다.

단순히 생각하면 for문을 두번 쓰기 때문이다.

# Swap 구현하기

 void swap(int *ptr1, int *ptr2)
  {
      int temp;
      temp = *ptr1;
      *ptr1 = *ptr2;
      *ptr2 = temp;
  }

버블정렬 / 선택정렬 / 삽입정렬 모두 배열에서 자리를 바꾸는 행위를 해야한다.

Swap함수는 int형 변수의 주소를 2개 받아 그 주소에 변수를 바꿔서 넣는 것으로 구현했다.

문제 상황은 n개의 수를 입력받아서 arr[]배열에 넣어둔 후 부터 시작이다.

n개의 수는 중복되지 않는다 자세한 내용은 백준 2750번 문제를 참고하자

# 버블정렬 구현하기

   for(int i=0;i<n;i++)
   {
       for(int j=0;j<n-1-i;j++)
       {
           if(arr[j]>arr[j+1])
           {
               swap(arr+j, arr+(j+1));
           }
       }
   }

버블정렬은 {1번,2번} {2번,3번} … 이런식으로 비교해 나가며 큰수를 밀어내는 방식이다 그러면 마지막 수는 제일 큰수가 가게 되고 다음 반복할때는 마지막 배열-1 까지 for문을 실행하게 된다.

# 선택정렬 구현하기

   int min;
   int *ptr1;
   for(int i=0;i<n;i++)
   {
       min = arr[i];
       ptr1 = &arr[i];
       for(int j=i;j<n;j++)
       {
           if(arr[j]<min)
           {
               min = arr[j];
               ptr1 = &arr[j];
           }
       }
       swap(arr+i, ptr1);
   }

선택정렬은 처음부터 끝까지 최소값 찾고 그 최소값을 제일 앞에 두는 방식이다

그러면 다음에 반복할 때는 두번째 부터 최소값을 찾기 시작한다.

# 삽입정렬 구현하기

   for(int i=1; i<n;i++)
   {
       for(int j=i;j>0;j--)
       {
           if(arr[j]<arr[j-1])
           {
               swap(arr +j, arr+(j-1));
           }
           else break;
       }
   }

삽입정렬은 자기 왼쪽에 자기보다 큰수가 있다면 자리를 바꾸는 방식이다.

2번 자리 부터 시작해서 왼쪽의 수들을 정렬하는 식으로 구현했다.