Quicksort in C++

// cat quicksort.cc

#include <bits/stdc++.h>
#include <algorithm>    // std::swap

using namespace std;

int partition(int arr[], int low, int high);

void qsort(int arr[], int start, int end)
{
    int p;
    if (start < end)
    {
        p = partition(arr, start, end);
        qsort(arr, start, p - 1);
        qsort(arr, p + 1, end);
    }
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];
    int i = low;
    int j = high + 1;

    do {
        do {
            i++;
        } while (arr[i] < pivot && i <= high);

        do {
            j--;
        } while(arr[j] > pivot);

        if (i < j)
            swap(arr[i], arr[j]);

    } while (i < j);
    swap(arr[low], arr[j]);
    return j;
}
int main()
{
    int arr[] = {11,2,100,1,2,31};

    size_t size = sizeof(arr)/sizeof(arr[0]);
    qsort(arr, 0, size - 1);

    for (int i = 0; i < size; i++)
        cout << arr[i] << endl;
}                                     

Reference


Codility: Maxed Counters Problem

Problem

You are given N counters, initially set to 0, and you have two possible operations on them:

> -   _increase(X)_  − counter X is increased by 1,
> -   _max counter_  − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

> -   if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
> -   if A[K] = N + 1 then operation K is max counter.

Solution

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N, A):
    # write your code in Python 3.6
    C = [0]*N
    cur_max = 0
    maxed = False
    last_max = 0
    
    for c in A:
        index = c - 1
        if c <= N:
            if maxed and (C[index] < last_max):
                C[index] = last_max

            C[index] += 1
            
            if C[index] > cur_max:
                cur_max = C[index]
            # print("incr", C)    

        if c == (N + 1):
            maxed = True
            last_max = cur_max
            # print("max", C)
            
    index = 0
    for c in C:
        if last_max > C[index]: 
            C[index] = last_max 
        index += 1

    return C

Reference

Written with StackEdit.