Cerinta completa

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of . In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort). This challenge is a modified version of the algorithm that only addresses partitioning. It is implemented as follows:

Step 1: Divide
Choose some pivot element, , and partition your unsorted array, , into three smaller arrays: , , and , where each element in , each element in , and each element in .

Example

In this challenge, the pivot will always be at , so the pivot is .

is divided into , , and .
Putting them all together, you get . There is a flexible checker that allows the elements of and to be in any order. For example, is valid as well.

Given and , partition into , , and using the Divide instructions above. Return a 1-dimensional array containing each element in first, followed by each element in , followed by each element in .

Function Description

Complete the quickSort function in the editor below.

quickSort has the following parameter(s):

  • int arr[n]: is the pivot element

Returns

  • int[n]: an array of integers as described above

Input Format

The first line contains , the size of .
The second line contains space-separated integers (the unsorted array). The first integer, , is the pivot element, .

Constraints

  • where
  • All elements are distinct.

Sample Input

STDIN       Function
-----       --------
5           arr[] size n =5
4 5 3 7 2   arr =[4, 5, 3, 7, 2]

Sample Output

3 2 4 5 7

Explanation


Pivot: .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

Return the array .

The order of the elements to the left and right of does not need to match this answer. It is only required that and are to the left of , and and are to the right.

Limbajul de programare folosit: python3

Cod:

#!/bin/python3

def quickSort(arr):
    p = arr[0]
    left = [x for x in arr if x < p]
    equal = [x for x in arr if x == p]
    right = [x for x in arr if x > p]
    return left + equal + right

if __name__ == '__main__':
    _ = int(input().strip())
    arr = list(map(int, input().split()))
    print(*quickSort(arr))

Scor obtinut: 1.0

Submission ID: 464589969

Link challenge: https://www.hackerrank.com/challenges/quicksort1/problem

Quicksort 1 – Partition