FilesExpand file tree

 master

/

quicksort.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (44 loc) · 794 Bytes

 master

/

quicksort.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (44 loc) · 794 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

#include <iostream>

#include <vector>

using namespace std;

void QuickSort(int arr[], int left, int right)

{

int i = left, j = right;

int tmp;

int pivot = arr[right];

/* partition */

while (i <= j) {

//pivot과 같아도 빠져나가기 때문에 배열범위를 넘어서는 일은 없다

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

//찾았다

if (i <= j) {

tmp = arr[i];

arr[i] = arr[j];

arr[j] = tmp;

//이게중요하다

i++;

j--;

}

};

/* recursion */

if (left < j)

QuickSort(arr, left, j);

if (i < right)

QuickSort(arr, i, right);

}

int main()

{

int n;

vector<int> v;

scanf("%d", &n);

v.resize(n);

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

scanf("%d", &v[i]);

QuickSort(&v[0], 0, v.size() -1);

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

printf("%d ", v[i]);

return 0;

}