Skip to content

leet code

2944 - Sort an Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// bubble sort

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int tmp=0;
        int size = nums.size();
        for(int i=0; i<size-1; ++i)
        {
            for(int j=0; j<size-1-i; ++j)
            {
                if(nums[j] > nums[j+1])
                {
                    tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
            }
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// selection sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int size = nums.size();
        int tmp=0;
        for(int i=0; i<size; ++i)
        {
            int maxVal = nums[0];
            int maxIdx = i;
            for(int j=i; j<size; ++j)
            {
                if(nums[j] < maxVal)
                {
                    maxVal = nums[j];
                    maxIdx = j;
                }
            }

            tmp = nums[maxIdx];
            nums[maxIdx] = nums[i];
            nums[i] = tmp;
        }

        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// insertion sort
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int tmp=0;
        int size = nums.size();
        for(int i=1; i<size; ++i)
        {
            int idx = i;
            while(idx > 0)
            {
                if(nums[idx] < nums[idx-1])
                {
                    tmp = nums[idx];
                    nums[idx] = nums[idx-1];
                    nums[idx-1] = tmp;
                }else
                {
                    break;
                }
                idx--;
            }
        }
        return nums;
    }
};

시도해 볼 리스트

  • merge sort(bottom up)
  • merge sort(top down)
  • quick sort(random pivot)

tim sort도 해보고 싶지만 생략