I am dosa.

정렬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번 자리 부터 시작해서 왼쪽의 수들을 정렬하는 식으로 구현했다.

Leave a comment

2024

D&C Optimization

3 minute read

분할정복을 이용한 다이나믹 프로그래밍 최적화

Back to top ↑

2023

Back to top ↑

2022

Greedy

2 minute read

백준 18186번 라면사기(large) 문제풀이

SCC

1 minute read

백준 4196번 도미노 문제풀이

LCA

2 minute read

백준 3176번 도로 네트워크 문제풀이

2-SAT

1 minute read

백준 16367번 TV Show Game 문제풀이

Hashing

2 minute read

백준 21162번 뒤집기 K 문제풀이

Tree DP

1 minute read

백준 1949번 우수 마을 문제풀이

Trie

1 minute read

Trie 자료구조 이해하기

Merge Sort

1 minute read

merge sort를 이용하여 inversion 개수세기

Segment Tree

2 minute read

백준 11505 구간 곱 구하기 문제풀이

BFS

1 minute read

백준 2206 벽 부수고 이동하기 문제풀이

기하

1 minute read

백준 2166 다각형의 면적 문제풀이

이분탐색

1 minute read

백준 12015 가장 긴 증가하는 부분 수열2 문제풀이

누적 합

1 minute read

백준 10986 나머지합 문제풀이

Stack

less than 1 minute read

스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택

정렬1

1 minute read

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

Back to top ↑