FilesExpand file tree

master

/

cocktail_sort.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

60 lines (49 loc) · 1.79 KB

master

/

cocktail_sort.py

Copy path

Top

File metadata and controls

• Code
• Blame

60 lines (49 loc) · 1.79 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

57

58

59

60

'''

Created by: Pratik Narola (https://github.com/Pratiknarola)

last modified: 14-10-2019

'''

def cocktail_sort(arr):

'''

Cocktail Sort is a variation of Bubble sort.

The Bubble sort algorithm always traverses elements from left

and moves the largest element to its correct position in first iteration

and second largest in second iteration and so on.

Cocktail Sort traverses through a given array in both directions alternatively.

This is an in-place sort.

:param arr: the array to sort

:return: the sorted array, which is the same reference as arr

'''

swapped = True

start = 0

end = len(arr) - 1

while swapped:

# reset the swapped flag on entering the loop,

# because it might be true from a previous

# iteration.

swapped = False

# loop from left to right same as the bubble

# sort

for i in range(start, end):

if arr[i] > arr[i + 1]:

arr[i], arr[i + 1] = arr[i + 1], arr[i]

swapped = True

# if nothing moved, then array is sorted.

if not swapped:

break

# otherwise, reset the swapped flag so that it

# can be used in the next stage

swapped = False

# move the end point back by one, because

# item at the end is in its rightful spot

end -= 1

# from right to left, doing the same

# comparison as in the previous stage

for i in range(end - 1, start - 1, -1):

if arr[i] > arr[i + 1]:

arr[i], arr[i + 1] = arr[i + 1], arr[i]

swapped = True

# increase the starting point, because

# the last stage would have moved the next

# smallest number to its rightful spot.

start = start + 1

return arr