Skip to content

Instantly share code, notes, and snippets.

View sudheesh001's full-sized avatar

Sudheesh Singanamalla sudheesh001

412 followers · 31 following
View GitHub Profile
@sudheesh001
sudheesh001 / MergeSort.md
Created July 7, 2013 11:20
Algorithm for Iterative Merge Sort

This is the algorithm you could be using for a Bottom Up, Non recursive method to write mergesort. Its faster. If you wish to see the time difference between both. Use the functions from the header file or to calculate and you'll see Iteration is faster. Though it could be slightly maddening near the end of the algorithm, give it a shot. Prior to invoking this algorithm run a sort for the first two elements of the array i.e array[0] and array[1] Time complexity O(nlogn)

FUNCTION MERGESORT(A, length)
  IF length < 2 THEN
		//RETURN everything because THE ARRAY IS ALREADY SORTED
		RETURN
	jump := 1
	WHILE jump < length DO
 startL := 0
@sudheesh001
sudheesh001 / K-Way Merge.md
Last active December 19, 2015 12:39
Complexity and Pseudocode for a K-Way merge algorithm.

For the base case we have something a little less trivial since our smallest merge will have k elements in it, which for a large data set could have 10 to 50 partitions OR MORE. To solve this we can sort by putting them in to a heap real quick and pulling them back out, in the given source code below, I didn't write the heap, but it's pretty trivial to do so.

if (high < low + k) {
    // the subarray has k or fewer elements
    // just make one big heap and do deleteMins on it
    Comparable[] subarray = new MergesortHeapNode[high - low + 1];
    for (int i = 0, j = low; i < subarray.length; i++, j++) {
        subarray[i] = new MergesortHeapNode(data[j], 0);
 }
@sudheesh001
sudheesh001 / curses.h
Created August 4, 2013 06:08
Curses.h Library, replacement to gotoxy() and clrscr()
/* $NetBSD: curses.h,v 1.103.2.1 2012/05/23 10:07:31 yamt Exp $ */
/*
* Copyright (c) 1981, 1993, 1994
* The Regents of the University of California. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
@sudheesh001
sudheesh001 / Treap.cpp
Created September 19, 2013 03:19
Treap implementation in C++
#include <iostream>
#include <cstdlib>
using namespace std;
// Assuming all the treap structure is correct.
//------------Rotations---------------------------------------------
/* RR(Y rotates to the right):
k2 k1
/ \ / \
k1 Z ==> X k2
@sudheesh001
sudheesh001 / queue.cpp
Created October 18, 2013 07:44
C++ implementation of queue
#include <iostream>
using namespace std;
template <class etype>
class queue
{
class qnode
{
public:
etype element;
@sudheesh001
sudheesh001 / Dijkistra.cpp
Created October 18, 2013 07:45
Shortest path algorithm, Make sure to include the queue.cpp file present here in the same folder as that of this cpp file. Queue.cpp => https://gist.github.com/sudheesh001/7037878
#include <iostream>
#include "queue.cpp"
using namespace std;
const int INFINITY = 999;
class graph
{
class vertex
{
public:
@sudheesh001
sudheesh001 / SingleDFS.cpp
Created November 21, 2013 05:21
Strongly Connected Components using single DFS. Print Code segment.
void Graph::printSCCs()
{
stack<int> Stack;
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
for(int i = 0; i < V; i++)
if(visited[i] == false)
fillOrder(i, visited, Stack);
Graph gr = getTranspose();
@sudheesh001
sudheesh001 / Working method.md
Created December 1, 2013 18:35
Easy Understanding of Pseudo-classes selectors in CSS3

Explanation to the working.

a.homepage:link, a.homepage:visited {
   ...
   }

This is basically setting the CSS rule for an anchor (link) in the class homepage in two stages,

@sudheesh001
sudheesh001 / messages.cpp
Created January 10, 2014 03:07
Messages and Locales are used in localization of content.
#include <iostream>
#include <locale>
int main()
{
std::locale loc("de_DE");
auto& facet = std::use_facet<std::messages<char>>(loc);
const char* dir = "/usr/share/gcc-data/x86_64-pc-linux-gnu/4.6.1/locale";
auto cat = facet.open("libstdc++", loc, dir);
std::cout << "\"please\" in German: "
<< facet.get(cat, 0, 0, "please") << '\n'
@sudheesh001
sudheesh001 / index.html
Created May 28, 2014 12:44
Vibe - Mozilla India
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Event Portal | Mozilla Vibe</title>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>
</head>
<body>
<script type="text/javascript">
var dateToday = new Date();