FilesExpand file tree

 patch-1

/

BitonicSort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

56 lines (42 loc) · 1.59 KB

 patch-1

/

BitonicSort.py

Copy path

Top

File metadata and controls

• Code
• Blame

56 lines (42 loc) · 1.59 KB

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

54

55

56

# Python program for Bitonic Sort. Note that this program

# works only when size of input is a power of 2.

# The parameter dir indicates the sorting direction, ASCENDING

# or DESCENDING; if (a[i] > a[j]) agrees with the direction,

# then a[i] and a[j] are interchanged.*/

def compAndSwap(a, i, j, dire):

if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] < a[j]):

a[i], a[j] = a[j], a[i]

# It recursively sorts a bitonic sequence in ascending order,

# if dir = 1, and in descending order otherwise (means dir=0).

# The sequence to be sorted starts at index position low,

# the parameter cnt is the number of elements to be sorted.

def bitonicMerge(a, low, cnt, dire):

if cnt > 1:

k = int(cnt / 2)

for i in range(low, low + k):

compAndSwap(a, i, i + k, dire)

bitonicMerge(a, low, k, dire)

bitonicMerge(a, low + k, k, dire)

# This funcion first produces a bitonic sequence by recursively

# sorting its two halves in opposite sorting orders, and then

# calls bitonicMerge to make them in the same order

def bitonicSort(a, low, cnt, dire):

if cnt > 1:

k = int(cnt / 2)

bitonicSort(a, low, k, 1)

bitonicSort(a, low + k, k, 0)

bitonicMerge(a, low, cnt, dire)

# Caller of bitonicSort for sorting the entire array of length N

# in ASCENDING order

def sort(a, N, up):

bitonicSort(a, 0, N, up)

# Driver code to test above

a = []

n = int(input())

for i in range(n):

a.append(int(input()))

up = 1

sort(a, n, up)

print("\n\nSorted array is")

for i in range(n):

print("%d" % a[i])