Convert array into Zig-Zag fashion - GeeksforGeeks
Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.
http://mathbits.com/MathBits/Java/arrays/Bubble.htm
http://www.algolist.net/Algorithms/Sorting/Bubble_sort
Given an array of distinct elements, rearrange the elements of array in zig-zag fashion in O(n) time. The converted array should be in form a < b > c < d > e < f.
Example:
Input: arr[] = {4, 3, 7, 8, 6, 2, 1} Output: arr[] = {3, 7, 4, 8, 2, 6, 1}
Input: arr[] = {1, 4, 3, 2} Output: arr[] = {1, 4, 2, 3}
The idea is to use modified one pass of bubble sort. 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. Let us see the main logic using three consecutive elements A, B, C. Suppose we are processing B and C currently and the current relation is ‘<'. But we have B > C. Since current relation is ‘<' previous relation must be '>‘ i.e., A must be greater than B. So, the relation is A > B and B > C. We can deduce A > C. So if we swap B and C then the relation is A > C and C < B. Finally we get the desired order A C B
voidzigZag(intarr[],intn){// Flag true indicates relation "<" is expected,// else ">" is expected. The first expected relation// is "<"boolflag =true;for(inti=0; i<=n-2; i++){if(flag)/* "<" relation expected */{/* If we have a situation like A > B > C,we get A > B < C by swapping B and C */if(arr[i] > arr[i+1])swap(arr[i], arr[i+1]);}else/* ">" relation expected */{/* If we have a situation like A < B < C,we get A < C > B by swapping B and C */if(arr[i] < arr[i+1])swap(arr[i], arr[i+1]);}flag = !flag;/* flip flag */}}
A Simple Solution is to first sort the array. After sorting, exclude the first element, swap the remaining elements in pairs. (i.e. keep arr[0] as it is, swap arr[1] and arr[2], swap arr[3] and arr[4], and so on). Time complexity is O(nlogn) since we need to sort the array first.
http://mathbits.com/MathBits/Java/arrays/Bubble.htm
In the bubble sort, as elements are sorted they gradually "bubble" (or rise) to their proper location in the array, like bubbles rising in a glass of soda. The bubble sort repeatedly compares adjacent elements of an array. The first and second elements are compared and swapped if out of order. Then the second and third elements are compared and swapped if out of order. This sorting process continues until the last two elements of the array are compared and swapped if out of order.
 | |
When this first pass through the array is complete, the bubble sort returns to elements one and two and starts the process all over again. So, when does it stop? The bubble sort knows that it is finished when it examines the entire array and no "swaps" are needed (thus the list is in proper order). The bubble sort keeps track of the occurring swaps by the use of a flag.
| |
public void bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++)
{
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
Read full article from Convert array into Zig-Zag fashion - GeeksforGeeks