정올 실력키우기 1814 : 삽입정렬 횟수 세기

코드

#include<iostream>

using namespace std;

void insert(int* arr, int num);

void Insertion_sort(int* arr, int num);

int main()

{

//수열의 길이를 받아들이는 변수 선언 및 값 입력

int num = 5;

cin >> num;

//배열 동적할당;

int* arr = new int[num];

//입력 값의 범위

if (num < 1 || num>50) return 0;

//수열의 값 입력 함수

insert(arr, num);

//삽입 정렬

Insertion_sort(arr, num);

//배열 동적할당 해제

delete[] arr;

}

//수열의 값 입력 함수

void insert(int * arr, int num)

{

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

{

cin >> arr[i];

//수열의 값 범위

if (arr[i] < -1000 || arr[i]>1000) exit(1);

}

}

//삽입 정렬

void Insertion_sort(int* arr, int num)

{

int temp  = 0;

int count = 0; //이동 횟수를 저장할 변수 선언

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

{

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

{

if (arr[j-1] > arr[j]) //만약 값이 작다면 이동

{

temp   = arr[j];

arr[j]     = arr[j-1];

arr[j - 1] = temp;

count++; //이동 횟수 측정

}

}

}

cout << count << '\n'; //이동 횟수 출력

}

문제 출처

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1087&sca=2060