선택정렬, 삽입정렬 복습 (1, 2주차)

우선순위 큐 :  삽입은 자유롭지만 삭제할 때 우선순위가 높은 거부터 삭제하는 큐

---

선택정렬 (코드는 오름차순)

모든 요소 순회해서 최댓값을 찾은 후 맨 뒤로 보낸다.

 

[ 내가 실수한 코드 ]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#pragma warning(disable:4996)

int main() {
    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    for (int i = n-1; i >0 ; i--)
    {
        int max_index = i;
        for (int j = i-1; j >=0; j--)
        {
            if (arr[max_index] < arr[i])  // 실수: arr[j] 이다 i 아니고 j 이다.
            {
                int tmp = arr[max_index];     // 실수: for문 다 돌아서 최댓값 인덱스 찾고 한 번만 swap 하는 거다 저렇게 하면 심히 비효울적이다. 
                arr[max_index] = arr[i];
                arr[i] = arr[tmp];

                max_index = i;
            }
        }
    }

    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

 

 

[ 정답 코드 ]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int main() {

	int n;
	scanf("%d", &n);

	int* arr = (int*)malloc(n * sizeof(int));  // c언어에서 배열 동적할당 할 때는 n * sizeof(int) 이렇게 해야 한다

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = n-1; i >= 1; i--)     // 맨 끝에서부터 채우는 경우: i = n-1; i>=1; 
	{                                  // 내가 한 실수: i<= 1;  이거 아니고  i>= 1;
    
		int max_index = i;    // 최댓값 저장 변수와 최댓값 인덱스 저장 변수
		for (int j = i-1; j >= 0; j--)
		{
			if (arr[max_index] < arr[j])
			{
				max_index = j;
			}
		}
		int tmp = arr[i];             // tmp = arr[i] 이거든 tmp = arr[max_index] 이거든 다 똑같다.
		arr[i] = arr[max_index];  // 차이는 swap방향이 시계방향이냐 반시계방향이냐 이다.
		arr[max_index] = tmp;
	}

	for (int i = 0; i < n; i++)
	{
		printf(" %d", arr[i]);
	}

	return 0;
}

 

 

 

삽입정렬 (코드는 오름차순)

앞에 있는 요소와 비교하여 맞는 자리를 찾을 때까지 움직인다.

 

 

[ 내가 실수한 코드 ]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#pragma warning(disable:4996)

int main() {
    int n;
    scanf("%d", &n);

    int* arr = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    for (int i = 1; i < n; i++)
    {
        for (int j = i; j >0; j--)
        {
            if (arr[j] < arr[j-1])   // 실수: if문 안 씀.. 아놔 기본은 지키시죠
            {
		int tmp = arr[j];
		arr[j] = arr[j - 1];
		arr[j - 1] = tmp;
            }
        }
    }


    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

 

 

[ 정답 코드 ]

밑에 있는 코드는 이중 for문 버전

(for + while 문으로도 할 수 있는데 while문이 들어가면 i-- 이런거 따로 해줘야 돼서 이중 for문이 한눈에 보기 더 깔끔하다.)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int main() {

	int n
	scanf("%d", &n);

	int* arr = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = 1; i < n; i++)         // 삽입정렬은 i=1 부터 시작 arr[0]은 고정
	{
		for (int j = i; j > 0; j--)    // 자기 자신부터 시작해서 j>0 까지 
		{
			if (arr[j] < arr[j-1])    // 둘 다 j 이다. i로 하면 안 됨. 
			{                         // arr[i] 값의 인덱스가 이동하면서 계속 바뀌기 때문이다.
				int tmp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = tmp;
			}
		}
	}


	for (int i = 0; i < n; i++)
	{
		printf(" %d", arr[i]);
	}

	return 0;
}

 

 

 

( for + while문은 참고만 하자 )

13455672  -->  13455677  -->  13455667 -->       ...      -->  13345567  -->  12345567

 

j <-pass-1 이   for문 기준 초기값

(j>=0)        이   for문 기준 조건문

j <- j-1       이   for문 기준 증감식

 

마지막에 save 넣는 인덱스가  j + 1 이다.  이거 조심하기

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#pragma warning(disable:4996)

int main() {

	int n, tmp; 
	scanf("%d", &n);

	int* arr = (int*)malloc(n * sizeof(int));

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	for (int i = 1; i < n; i++)
	{
            save = arr[i];
            int j = i-1;
            while((j>=0) && (arr[j] > save)){
               arr[j+1] = arr[j];            // 큰 걸  뒤로 이동시키고
               j -= 1;
            }
            arr[j+1] = save;    // 원래 큰 거 자리에 save 넣기 ,  **** j+1 이다. ****
	}


	for (int i = 0; i < n; i++)
	{
		printf(" %d", arr[i]);
	}

	return 0;
}