Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Pseudocode
2.2.
Implementation
2.2.1.
Time complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is the sorting algorithm in data structure?
3.2.
What is the syntax of an array?
3.3.
What is Linear data structure?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

Alternative Sorting

Author Sagar Mishra
2 upvotes

Introduction

Alternative sorting is a format where the array is printed in a particular manner. It is important to note that it is not a Sorting technique as the name suggests but rather an array representation. 

In this article, we will discuss the problem of Alternative sorting along with its time complexity and auxiliary space.

Problem Statement

We have a given integer array of length N. Now, use the alternative sorting technique to rearrange and display the output array. The required output should look in such a manner that the largest element is positioned in the first position (index 0), and the smallest element is placed in the second position (index 1). Similarly, the second largest element is positioned at the third position (index 2), and second smallest element on the fourth (index 3), and so on.

Sample Examples

Example 1:

                                                     

                                                     

 

Example 2:

                                                       

                                                       

Approach

  1. Sort the given array using any algorithm like merge sort, quick sort, etc., keeping in mind that the time complexity should be O(n log(n)).
  2. Place two pointers in the array, first at the starting element (0th index) and the other at the last(n-1th index), representing the maximum and minimum.
  3. Then alternatively, print elements pointed by two-pointers and move them toward each other.

Pseudocode

Input Array: 
myArr[] = {5, 3, 7, 1, 6, 0, 8, 9}
Sorted Array: 
MyArr[] = {0, 1, 3, 5, 6, 7, 8, 9}
int i=0, j=n-1;
while(i<j){
print(arr[j--]+" ");
print(arr[i++]+" ");
}
if(n%2 != 0){
    print(arr[i]);
}

Implementation

#include <iostream>
using namespace std;

//swap the elements
void swap(int *a, int *b) 
{
    int t = *a;
    *a = *b;
    *b = t;
}

// function to rearrange array
int partition(int array[], int low, int high) 
{
    int pivot = array[high];
    int i = (low - 1);

  // traverse each element of the array
  // compare them with the pivot
    for (int j = low; j < high; j++) 
    {
        if (array[j] <= pivot) 
        {
            i++;
            swap(&array[i], &array[j]);
        }
    }
  
  //now, swap pivot with the greater element at i
    swap(&array[i + 1], &array[high]);
    return (i + 1);
}

void sort(int array[], int low, int high) 
{
    if (low < high) 
    {
        // find the pivot element so
        // elements smaller than the pivot are on the left of the pivot
        // and elements greater than the pivot are on the right of the pivot
        int pi = partition(array, low, high);
    
        // recursive call on the left of the pivot
        sort(array, low, pi - 1);
    
        // recursive call on the right of pivot
        sort(array, pi + 1, high);
    }
}

// Function to perform Alternative Sorting
void alternateSort(int arr[], int n)
{
    // Sort the array by quick Sort
    sort(arr, 0, n-1);
 
    //Print the element in the alternative order
    int i = 0, j = n-1;
    while (i < j) {
        cout << arr[j--] << " ";
        cout << arr[i++] << " ";
    }
    
    // If the total element in given array is odd 
    //print the last middle element.
    if (n % 2 != 0)
        cout << arr[i];
}

// function to print the array
void printArray(int array[], int size) {
  int i;
  for (i = 0; i < size; i++)
    cout << array[i] << " ";
  cout << endl;
}
// Main
int main() {
  int arr[] = {8, 1, 12, 4, 6, 7, 10, 5};
  int n = sizeof(arr) / sizeof(arr[0]);
  alternateSort(arr, n);
}

Output

Time complexity

The time complexity of the given problem is O(n log(n)), where ‘n’ is the length of the array.

Space Complexity

The time complexity of the given problem is O(1).

Also see,  Rabin Karp Algorithm

Refer to know about :  Topological sort

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the sorting algorithm in data structure?

A sorting algorithm is a technique of rearranging the values of a list in a particular order, that is, ascending order or descending order. There are a lot of sorting algorithms present in the data structure like Merge sort, quick sort, etc. 

What is the syntax of an array?

Declaring an array is a simple task, i.e., VariableType variableName[d1, d2,..dn] where d is the dimension of the array and example of VariableType is int, float, bool, etc.

What is Linear data structure?

Linear Data Structure is a collection of data values with the same data types stored in a contiguous memory location. An array is an example of a Linear Data Structure.

Conclusion

We have extensively discussed Alternative Sorting in this article. We started with introducing the Alternative Sorting, problem statement, example, and implementation, and finally concluded with the time complexity of the algorithm.

We hope that this blog has helped you enhance your knowledge regarding how to generate all possible sorted arrays from alternate elements of two given sorted arrays and if you would like to learn more, check out our other articles on the problem like custom sort stringQuick sort on Doubly Linked ListDoubly Linked List, Merge Sort for Doubly Linked List, and many more on our platform Coding Ninjas Studio.

Recommended Problems -

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

 

 

Previous article
Sort an Array in Waveform
Next article
Smallest Index with Equal Value
Live masterclass