Algorithm | Convert array into Zig-Zag fashion

• Maintain a flag for representing which order(i.e. < or >) currently we need.
• If the current two elements are not in that order then swap those elements otherwise not.

zigzag

def zigzag(arr):
    flag = True #arr[i]>arr[i+1]
    for i in range(len(arr)-1):
        if i == 0:
            if arr[i]<arr[i+1]:
                continue
            flag = bool(1-flag)
            continue
        if flag:
            if arr[i]<arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
        elif not flag:
            if arr[i]>arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
        flag = bool(1-flag)

##sort algorithm
###Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
https://www.geeksforgeeks.org/bubble-sort/

• original complexity: O(n^2) time
• optimization: stop the algorithm if inner loop didn’t cause any swap.
  • Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
  • Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
  • Auxiliary Space: O(1)
  • Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

###Quick Sort
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

quicksort

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

####there are many kinds of partition

• https://www.geeksforgeeks.org/quick-sort/ : takes last element as pivot. Run i from left to right-1, intialize the partition index as j=left-1. If arr[i]<arr[pivot], swap i and j, j++, because after swapping, arr[j]<arr[pivot]. Else, no swapping and no j++. return j as index.

• https://www.runoob.com/w3cnote/quick-sort-2.html : take the first element as pivot. Run i from left+1 to right, initialize the position of partition index as j=i. If arr[i] right, swap j-1 and pivot, return j-1 as index.

• https://leetcode-cn.com/problems/decrease-elements-to-make-array-zigzag/solution/ : take a random element as pivot and move it to the last. Initialize i=left, j=left-1. Ensure at anytime, following requirements are satisfied:

  • l<=k<=j, arr[k]<=arr[pivot]
  • j+1<=k<=i-1, arr[k]>arr[pivot]

time complexity: O(nlogn)
space complexity: O(h)