[BOJ] 1083번 소트

복기

버블정렬은 내부 반복문이 끝날 때마다 자리 하나가 고정이 된다.

코드

• C++ 17

#include <iostream>   #define min(a, b) (a < b) ? a : b   using namespace std;   int N, S; int Arr[50];   int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     cout.tie(nullptr);       cin >> N;     for (size_t i = 0; i < N; i++)         cin >> Arr[i];     cin >> S;       // 본 문제는 버블정렬을 이용하는 것이다.     // 반복이 끝나는 것은 정렬이 다 되었거나,     // 교환을 더 이상 할 수 없을 때다.     for (size_t i = 0; i < N; i++)     {         // 교환을 더 할 수 없으면 반복을 종료한다.         if (S == 0)             break;           // 현재 값을 최댓값으로 설정한다.         int max = Arr[i], maxIdx = i;           // 교환할 수 있는 횟수는 아래와 같다.         size_t count = min(N, i + 1 + S);         for (size_t j = i + 1; j < count; j++)         {             // 이동할 수 있는 범위에서 최댓값을 찾는다.             if (max < Arr[j])             {                 max = Arr[j];                 maxIdx = j;             }         }           // 버블정렬은 내부 반복문을 완료할 때마다         // 가장 상위값의 자리가 고정이 된다.         // 그러므로 그 값이 이동한 횟수만큼 차감한다.         S -= maxIdx - i;           // 값을 반영한다.         for (size_t j = maxIdx; j > i; j--)             Arr[j] = Arr[j - 1];         Arr[i] = max;     }       for (size_t i = 0; i < N; i++)         cout << Arr[i] << ' '; }

• C# 6.0

using System;   namespace Csharp {     class Program     {         static void Main(string[] args)         {             int N = Convert.ToInt32(Console.ReadLine());             int[] arr = new int[N];             var nums = Console.ReadLine().Split();             for (int i = 0; i < N; i++)             {                 arr[i] = Convert.ToInt32(nums[i]);             }             int S = Convert.ToInt32(Console.ReadLine());               for (int i = 0; i < N - 1; i++)             {                 if (S == 0)                     break;                   int max = arr[i], maxIdx = i;                 int count = Math.Min(N, i + 1 + S);                 for (int j = i + 1; j < count; j++)                 {                     if (max < arr[j])                     {                         max = arr[j];                         maxIdx = j;                     }                 }                 S -= maxIdx - i;                   for (int j = maxIdx; j > i; j--)                     arr[j] = arr[j - 1];                 arr[i] = max;             }               for (int i = 0; i < N; i++)                 Console.Write($"{arr[i]} ");         }     } }

• Python 3

from sys import stdin input = stdin.readline   N = int(input()) arr = list(map(int, input().split())) S = int(input())   for i in range(N - 1):     if S == 0:         break       max, idx = arr[i], i     for j in range(i + 1, min(N, i + 1 + S)):         if max < arr[j]:             max = arr[j]             idx = j     S -= idx - i          for j in range(idx, i, -1):         arr[j] = arr[j - 1]          arr[i] = max   print(' '.join(map(str, arr)))