Waveform sorting of arrays using Python

In this article, we will learn a Python program for waveform sorting of an array.

Suppose we have an unsorted input array. We will now sort the input array in a waveform manner. If the array 'arr [0..n-1]' satisfies arr [0] >= arr [1] = arr [3] = . ...., the array is sorted into a waveform.

Methods Used

The following are various methods for accomplishing this task &miinus;

• Use the built-in sort() function

• Without Using Built-in functions

Method 1: Using the Built-in sort() function

Algorithm (steps)

Following are the Algorithms/steps to be followed to perform the desired task. −

• Create a function to sort the input array by waveform, accepting the input array and array length as parameters.

• Use the sort() function(sorts the list in ascending/descending order ) to sort the input array in ascending order.

• Use the for loop to traverse till the array length alternatively(step=2)

• Swap the adjacent elements i.e, current and its next using the ‘,’ operator.

• Create a variable to store the input array.

• Use the len() function (which returns the number of items in the object) to get the length of the input array.

• Call the above-defined sortingInWaveform() function by passing the input array, and length of the array as arguments

• Use for loopTraverse all elements of the array

• Print the current element of an array.

Example

The following program sorts the input array in waveform using the python Built-in sort() function −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # sorting the input array in ascending order using the sort() function
   inputArray.sort()
   # travsersing till the array length alternatively(step=2)
   for k in range(0, arrayLength-1, 2):
         # swapping the adjacent elements i.e, current and it's next
         inputArray[k], inputArray[k+1] = inputArray[k+1], inputArray[k]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
# printing the given array/list
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element of the array/list
      print(inputArray[k], end=" ")

Output

On execution, the above program will generate the following output &miinus;

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
4 3 12 6 25 15 68 45 70 

Time complexity − O(nLogn).

Here, the array that was given was sorted using the sort function, which typically has an O(NlogN) time complexity.

If you apply O(nLogn) sorting algorithm, such as Merge Sort, Heap Sort, etc., the time complexity of the above method is O(nLogn).

Method 2: Use only one loop

Algorithm (steps)

Following are the Algorithms/steps to be followed to perform the desired task. −

• Use the for loop to traverse through all the even index elements by passing 0, array length, and step value as arguments

• Use the if conditional statement to check whether the current even index element is smaller than the previous element.

• Swap the elements if the condition is true.

• Use if conditional statement to check whether the current even index element is less than the next element.

• Swap the elements if the condition is true.

• Call the above-defined sortingInWaveform() function by passing the input array, and length of the array as arguments

• Use for loop to traverse the elements of the array.

• Print the corresponding element of the array/list.

Example

The following program sorts the input array in wave form using only one for loop and without Built-in functions −

# creating a function to sort the array in waveform by accepting
# the input array, array length as arguments
def sortingInWaveform(inputArray, arrayLength):
   # traversing through all the even index elements
   for p in range(0, arrayLength, 2):
      # checking whether the current even index element
      # is smaller than the previous
      if (p > 0 and inputArray[p] < inputArray[p-1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p-1] = inputArray[p-1], inputArray[p]
            # checking whether the current even index element
            # is smaller than the next element
      if (p < arrayLength-1 and inputArray[p] < inputArray[p+1]):
         # swapping the elements if the condition is true
            inputArray[p], inputArray[p+1] = inputArray[p+1], inputArray[p]
# input array
inputArray = [12, 45, 15, 4, 6, 70, 68, 3, 25]
# getting the length of the input array
arrayLength = len(inputArray)
print("The Given list is:", inputArray)
# calling the above defined sortingInWaveform() function by
# passing input array, length of the array as arguments
sortingInWaveform(inputArray, arrayLength)
print("The Result Array after sorting in wave form is:")
# traversing through all the elements of the array
for k in range(0, arrayLength):
   # printing the current element
   print(inputArray[k], end=" ")

Output

After executing the above program, the following output will be generated -

The Given list is: [12, 45, 15, 4, 6, 70, 68, 3, 25]
The Result Array after sorting in wave form is:
45 12 15 4 70 6 68 3 25

Time complexity - O(n).

Here, we didn't use the sort function; instead, we just used the for loop to iterate through the elements of the given array, which, on average, has O(N) time complexity.

in conclusion

In this article, we learned how to sort a given array of waveforms using two different methods. We used a new logic whose time complexity is reduced by O(log N) compared to the first method. In many cases, these types of algorithms help reduce time complexity and implement efficient solutions.

The above is the detailed content of Waveform sorting of arrays using Python. For more information, please follow other related articles on the PHP Chinese website!